CF1458B Glass Half Spilled

題意：

有n杯水，第i杯有容積$a_i$單位，初始時(shí)裝有$b_i$單位的水
現(xiàn)在你可以進(jìn)行若干次操作,每次選擇一杯水的一定水量并倒到另一杯水中,但是因?yàn)檫@些杯子形狀非常奇怪,因此每倒一次水,倒的水會(huì)有一半灑在地上.
求出對(duì)于所有整數(shù)p滿足$1<=p<=n$,求出進(jìn)行若干次操作后選取p個(gè)杯子能獲得水單位數(shù)量的最大值

題解：

每次倒水都會(huì)有損失，那么倒水的過程肯定不能出現(xiàn)同樣的水來回倒，這樣必不優(yōu)。因此我們就直接選中p個(gè)杯子，讓后將其他杯子里的水都倒進(jìn)來。設(shè)選出的k個(gè)杯子的a值和為A且b值和為B，所有杯子的b值和為sumb?？梢缘玫酱鸢竚in{A,(sumb-B) * 0.5+B}=min{A,sumb * 0.5+B * 0.5}
現(xiàn)在我們就要求出對(duì)于每個(gè)A所對(duì)應(yīng)的盡可能大的B（因?yàn)锳是給出的，B不好求）
我們把A看作容積，把B看作價(jià)值，這不就是01背包，但本題A的容積不是固定的
A表示容積，而最多就100個(gè)杯子，每個(gè)杯子容積最大是100，也就是說A最大才10000，所以我們完全可以直接枚舉容積
因?yàn)轭}目問k個(gè)杯子的情況，所以我們還需要一維來記錄所選杯子數(shù)量
設(shè)dp[i][j]][k]:前i個(gè)杯子選了j個(gè)，且容積為k的最大價(jià)值(最大盛水容量)
我們可以通過滾動(dòng)數(shù)組優(yōu)化第一維
時(shí)間復(fù)雜度為$O(n^4)$

代碼：

#include <bits/stdc++.h> #include <unordered_map> #define debug(a, b) printf("%s = %d\n", a, b); using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> PII; clock_t startTime, endTime; //Fe~Jozky const ll INF_ll= 1e18; const int INF_int= 0x3f3f3f3f; void read(){}; template <typename _Tp, typename... _Tps> void read(_Tp& x, _Tps&... Ar) {x= 0;char c= getchar();bool flag= 0;while (c < '0' || c > '9')flag|= (c == '-'), c= getchar();while (c >= '0' && c <= '9')x= (x << 3) + (x << 1) + (c ^ 48), c= getchar();if (flag)x= -x;read(Ar...); } template <typename T> inline void write(T x) {if (x < 0) {x= ~(x - 1);putchar('-');}if (x > 9)write(x / 10);putchar(x % 10 + '0'); } void rd_test() { #ifdef ONLINE_JUDGE #elsestartTime = clock ();freopen("data.in", "r", stdin); #endif } void Time_test() { #ifdef ONLINE_JUDGE #elseendTime= clock();printf("\nRun Time:%lfs\n", (double)(endTime - startTime) / CLOCKS_PER_SEC); #endif } const int maxn=300; struct node{int a,b; }w[maxn]; int dp[102][10020]; int main() {//rd_test();int n;read(n);int sum=0;for(int i=1;i<=n;i++){cin>>w[i].a>>w[i].b;sum+=w[i].b;}memset(dp,-INF_int,sizeof dp);dp[0][0]=0;for(int i=1;i<=n;i++){for(int j=i;j>=1;j--){for(int k=10000;k>=w[i].a;k--){dp[j][k]=max(dp[j][k],dp[j-1][k-w[i].a]+w[i].b);}}}for(int i=1;i<=n;i++){double ans=0;for(int k=0;k<=10000;k++){ans=max(ans,1.0*min(1.0*k,0.5*sum+0.5*dp[i][k]));}printf("%.9lf ",ans); // cout<<ans<<endl;}return 0;//Time_test(); }

總結(jié)

以上是生活随笔為你收集整理的CF1458B Glass Half Spilled的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。