题目地址

https://codeforces.com/contest/1459/problem/D

题目大意

$n\leq 100$

有$n$个玻璃杯，有$a[i]$和$b[i]$两个属性，分别代表容量和里面已经有的水，转移水的时候会损失一半的水被撒到地上。

问把水集中到$k$个杯子里的时候，最多总共可以有多少水？$k=1,2,3,4\dots n$

解法

这题居然是一个几乎是裸的01背包！

有两种写法，先讲我一开始写的一种：

是两个限制条件的01背包$dp[i][j][k]$,第一维是“当只考虑前i个杯子时”，第二维是“取了几个杯子”，第三维是这些杯子里的初始水量$b[i]$之和。

这时候就可以开始按照裸01背包写了，$dp[i][j][k]$维护这个条件下最大的容量！为什么是最大的容量呢？因为选中的$k$个杯子中初始水量和相等的情况下，肯定是容量越大最后的结果也会越大(或者相等，但肯定不会小)。

考虑到空间复杂度，$dp$数组需要把第一维变成滚动的来节省空间。

在处理完$dp[j][k]$数组之后，只需要按照题意列出实际值，比较后得出结果即可

实际值也就是除去k个杯子外的总水量$\sum_{i=1}^{n} b[i]-k$除以2之后再加上k，即$k+(sum-k)/2$,这个值还要跟$dp[j][k]$取$min$,因为杯子的容量有限，最后就是$max(min(dp[j][k],k+(sum-k)/2))$。

——————————分割线———————————-

第二种方法就是k改成k个杯子的总容量

这个时候的结果就是$max(res,min(k,dp[j][k]+(sum-dp[j][k])/2))$

两个值得注意的点

1.因为有的杯子的初始水量为0，所以一开始开始$O(n^3)$求$dp[j][k]$的时候$k$也要从0开始。

2.因为有的杯子的初始水量为0，所以最后结果的循环要从0开始。

代码

解法1

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repb(i,a,b) for(int i=(a);i>=(b);i--)
const int MAXN = 114;
#define INF 0x3f3f3f3f
int cansel_sync=(ios::sync_with_stdio(0),cin.tie(0),0);
int dp[MAXN][10010];
int a[MAXN],b[MAXN];
int n,tot;
void solve(){
    cin>>n;
    tot = 0;
    rep(i,1,n){
        cin>>a[i]>>b[i];
        tot+=b[i];
    }
    memset(dp,-INF,sizeof(dp));
    dp[0][0]=0;
    rep(i,1,n){
        repb(j,i,1){
            repb(k,tot,0){//错在这里，因为可能有bi=0的情况
                if(k>=b[i]&&j) dp[j][k] = max(dp[j][k],dp[j-1][k-b[i]]+a[i]);
            }
        }
    }
    rep(j,1,n){
        double res = 0;
        rep(k,0,tot){//第二处错在这里，应该从0开始，因为k是水量不是容量，所以也可能为0
            res = max(res,min((double)dp[j][k],k+(double)(tot-k)/2));
        }
        cout<<res<<' ';
    }
    cout<<endl;
}
int main(){
    solve();
}

解法2

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repb(i,a,b) for(int i=(a);i>=(b);i--)
const int MAXN = 114;
#define INF 0x3f3f3f3f
int cansel_sync=(ios::sync_with_stdio(0),cin.tie(0),0);
int dp[MAXN][10010];
int a[MAXN],b[MAXN];
int n,tota,totb;
void solve(){
    cin>>n;
    tota = totb = 0;
    rep(i,1,n){
        cin>>a[i]>>b[i];
        tota+=a[i];
        totb+=b[i];
    }
    memset(dp,-INF,sizeof(dp));
    dp[0][0]=0;
    rep(i,1,n){
        repb(j,i,1){
            repb(k,tota,0){
                if(k>=a[i]&&j) dp[j][k] = max(dp[j][k],dp[j-1][k-a[i]]+b[i]);
            }
        }
    }
    rep(j,1,n){
        double res = 0;
        rep(k,0,tota){
            if(dp[j][k]>=0){
                res = max(res,min((double)k,(double)dp[j][k]+(double)(totb-dp[j][k])/2));
            }
        }
        cout<<res<<' ';
    }
    cout<<endl;
}
int main(){
    solve();
}