[南海云课堂] [贪心] [问题转换] [DP] 盘子

· · 个人记录

洛谷链接，题意一样。

题意

小明家举行聚会，邀请了很多同学参加，所以小明准备了很多盘子，装水果共同学们吃，由于来的同学比较多，所以小明不得不把果盘合并到一起，这样就可以腾出来很多盘子。

小明准备了n个盘子，每个盘子上面放了 a(i) 个水果，并且每个盘子都有一个容量 b(i)，任何时刻 a(i) 必须小于等于 b(i)，小明可以从一个盘子拿一个水果放到另一个盘子上面，操作花费 1 秒钟（可以进行任意次操作）。

请你帮小明算一下最少需要多少个盘子才能装的下所有的水果，以及该情况下所用的最少时间。

思路

注意第二问是建立在第一问的基础上的。

对于第一问，简单的贪心，从大到小取盘子即可，在此不过多赘述。

对于第二问，我们发现没必要将所有盘子上的水果都移动，固定住一些盘子，将其它水果转移至上面即可，这样做一定更优于前者。

那么时间花费便是：\sum\limits_{i=1}^{n} b_i-B，其中 B 是固定不动的盘子上的水果数之和。

于是问题被转换为求 \max B，显然可以通过 \rm{DP} 解决。

首先有前两位 i,j，表示前 i 个盘子中固定 j 个，这是为了与第一问契合。注意到 B 是合法的条件是这 j 个盘子的容量和能装下所有水果，于是需加上第三维 k。

总结起来就是 f_{i,j,k} 表示前 i 个盘子中固定 j 个，且总容量为 k 时，这 j 个盘子上原先至多有多少个水果。

容量、价值......这不就是个 01 背包吗？（与常规问题的唯一差异在于背包的容量越大越好，当然这没有影响）。

转移方程便是 f_{i,j,k}=\max f_{i-1,j-1,k-b_i}+a_i。

时间复杂度为 O(n^2\sum\limits_{i=1}^{n} b_i)。而 f 的第一位可滚动优化掉，空间复杂度便为 O(n\sum\limits_{i=1}^{n} b_i)。可过（时间跑不满啊）。

考试硬写题的后果是状态都不对，这个故事告诉我们要先从题目性质入手分析，死磕不一定能对。

代码

细节不算多，就只放 \rm{DP} 部分及答案部分咯。

//as、bs：a数组、b数组之和 
for(int i=1; i<=n;i++){
    for(int j=i; j>=1;j--){
        for(int k=bs; k>=0;k--){
            if(k>=c[i].b){ //合法状态才可转移 
                f[j][k]=max(f[j][k],f[j-1][k-c[i].b]+c[i].an);
            }
        }
    }
}
for(int k=as; k<=1e4+5;k++){
    ans2=min(ans2,as-f[ans1][k]); 
}
cout<<ans1<<' '<<ans2;