出题人题解 | #Rabbit的工作(2)#

原题解链接：https://ac.nowcoder.com/discuss/151166

背包

不知道有没有看出来这是一个完全背包的模型，把一个任务完成的天数当做物品，把$WW$天作为背包的容量(恰好背满),但是不太一样的就是这道题需要保证完成恰好$KK$个任务(所背物品数量的限制)，我们容易联想到三维$dpdp$，但是显然时间复杂度不允许。

那么我们考虑如何把数量这个限制去掉。

由于要完成$KK$个任务，那我们可以这么转化:先给每个任务分配一天，然后就没有数量的限制了，用剩下的$W-KW-K$天完全背包随意分配,再跟原来的一天去组合(所以除了一天以外的“物品”需要做一下差分)。

例如对于样例来说，我们先给三个任务分配一天，现在的总满意度为$3\ast 6=183*6=18$。

剩下两个“物品”差分后天数、满意度分别为{$1,2-61,2-6$}和{$2,4-62,4-6$}。然后用剩下的天数$22$去对这两个物品做一下完全背包求最大值即可。

#include <cstdio>
#include <bits/stdc++.h>
#include <map>
#include <cstring>
#include <algorithm>
using namespace std;
#define mst(a,b) memset((a),(b),sizeof(a))
#define rush() int T;scanf("%d",&T);while(T--)

typedef long long ll;
const int maxn = 2005;
const ll INF = 1e18;
const ll mod=1e9+7;
const double eps = 1e-9;

int n,k,w;
int val[maxn];
int dp[maxn];

int main()
{
    scanf("%d%d%d",&n,&k,&w);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&val[i]);
        if(i) val[i]-=val[0];
    }
    mst(dp,-1);
    dp[0]=k*val[0];
    w-=k;
    for(int i=1;i<n;i++)
    {
        for(int j=i;j<=w;j++)
        {
            if(~dp[j-i]) dp[j]=max(dp[j],dp[j-i]+val[i]);
        }
    }
    printf("%d\n",dp[w]);
}