Rabbit的工作(2)

题目链接

 中文题目，就不描述题意了
参考自

思路:

 这道题乍一看是一道重复背包问题,但是不同的是,它要求所有任务都要完成,也就是说有物品都要装进去,并且每一件物品的数量我们也不知道。这些不同会让我们无从下手,其实我们可以这样想:先把所有物品都花一天完成,所以还剩下W-K天没有分配，而剩下这些天数可以随便分配，没有数量限制（因为一个任务最少要1天，而我们上来就给了每个任务一天，所以给分配时，无需考虑是否有任务没做）也就是说,我们把在剩下w - k天中选择的方案分配给k个一天的方案,来组成最后的方案数

比如 有3个任务 要求6天恰好完成 那我先花三天把这些任务都做完 剩下3天分别选择了 2 ,1 天完成,那么我就把2,1这两个分配给三个任务中的两个,这样就解决了这个问题

 并且由于题目限制w <= 2 * k所以在对 w - k 天进行完全背包时,不需要担心我们最后选择的给k个任务分配的加权数会超过k(毕竟我全部选择一天的,剩下的w - k天也就最多k天)

注意给的满意度是指i天对应的满意值，而非第i天，所以我们要先处理一下，将每天的满意值减去第一天满意值（相当于第一天已分配）。由于是要求恰好用完w天,所以要给dp数组初值赋为-inf
最后再加上即可

code

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = 2e3 + 5;
const int inf = 0x7fffffff;
const int mod = 1e3;

int dp[2 * maxn],v[maxn];//dp[i,j],i天完成j项工作获得最大满意度
int n,k,w;//n天,k个任务,w容量

int main()
{
    cin>>n>>k>>w;
    for(int i = 1; i <= n; i++){
        cin>>v[i];
        if(i > 1) v[i] -= v[1];
    }
    w -= k;
    for(int i = 0; i <= w; i++) dp[i] = -inf;
    dp[0] = 0;
    for(int i = 2; i <= n; i++){
        for(int j = i - 1; j <= w; j++){
            dp[j] = max(dp[j],dp[j - i + 1] + v[i]);
        }
    }
    cout<<dp[w] + k * v[1]<<endl;
     return 0;
}