题解 P1687 【机器人小Q】

· · 题解

Analysis

感觉题意没写太清楚（所以贪心选前k个会挂）

应该不止我一人简单地将题意理解为：在n个物品中选k个，然后放到容量为119的背包里，要求用尽量少的背包。

然后看了看题解的线性dp思路，又仔细读了读题目，发现有这样两句模糊的描述：

而小 Q 的能量菜单表上已经按一定顺序给出了 N 个单位的能量值

他只想知道，若是想让小 Q 获得 k 单位的能量（也就是能量表中可以不接受某些能量）最少需要几天来充电。

"一定顺序"表明能量单位是按顺序来的；而如果你不接受某个能量单位，在以后就不能召回。

这表明我们在往背包里面放物品的时候，只能将当前物品放在当前背包里面。

也就是说，如果这一次你选择开个新的背包，那么前面那个背包就必须舍弃。

举个例子：1 1 118

那么当你处理到第三个物品，不得不开一个新的背包时，尽管第一个背包只用了2的容积，它也已经被你抛弃而无法继续使用。

所以贪心优化要排序并选取前k小，这一排序便会打乱顺序，也就挂了（这样也能有50pts数据是有多弱）。

而这也是线性dp成立的重要原因：考虑最小背包数a和最后一个背包的最小已用容积b两个因素，设计状态f_{i,j}表示在前i个物品中选择j个物品的pair<int,int>(a,b)的最小值。

则考虑选与不选有方程f_{i,j}=\min(add(f_{i-1,j-1},a_i),f_{i-1,j})，其中add返回的是向原pair放入一个物品后的pair。

具体细节看代码，主要用了个pair来简化思路：

#include<bits/stdc++.h>

#define gc() getchar()

#define ri register int 
#define pii pair<int,int>

#define inf 0x3f3f3f3f

using std::min;
using std::pair;
using std::make_pair;

inline int read()
{
    ri ret=0;char ch=gc();
    while(!isdigit(ch))ch=gc();
    while(isdigit(ch))
    {
        ret=ret*10+ch-'0';
        ch=gc();
    }
    return ret;
}

const int MAXN=3e3+10;
const int MOD=119;

int n,m;
int a[MAXN];
pii f[MAXN][MAXN];

//自定义一个加法函数，能放下就放，放不下就新开背包 
pii add(pii s,int x)
{
    if(s.second+x<=MOD)
        s.second+=x;
    else
    {
        ++s.first;
        s.second=x;
    }
    return s;
}

int main()
{
//  freopen("1.in","r",stdin);

    n=read();m=read();
    for(ri i=1;i<=n;++i)
    {
        a[i]=read();
        if(a[i]>MOD){--i;--n;}
    }
    if(n<m)
    {
        printf("You can't do it.\n");
        return 0;
    }

    for(ri i=0;i<=n;++i)
        for(ri j=0;j<=m;++j)
            f[i][j]=pii(inf,0);//不合法状态初始化为inf
    for(ri i=0;i<=n;++i)
        f[i][0]=pii(0,MOD);//初始状态为使用了0个背包，但第0个背包不能放物品 

    for(ri i=1;i<=n;++i)
        for(ri j=1;j<=m;++j)
            f[i][j]=min(add(f[i-1][j-1],a[i]),f[i-1][j]);
    printf("%d\n",f[n][m].first);

    return 0;
}