牛客网

文章目录

题目描述

Rabbit通过了上次boss的考核，现在她又遇到了一个问题。 Rabbit接到了K个任务，每个任务她可以自由选择用i天去完成(1≤ i≤
N)。刁钻的boss想让Rabbit恰好用W天完成所有任务。
已知Rabbit用i天完成一个任务能让boss获得的满意度为vi(因为完成任务的质量不同)，她想知道在满足boss要求的情况下能让boss获得的总满意度最大是多少。

输入描述:
第一行三个整数N，K，W。
第二行N个整数vi，vi表示用i天完成一个任务能让boss获得的满意度。
输出描述:
输出Rabbit在满足boss要求的情况下能让boss获得的总满意度最大是多少。
示例1
输入

3 3 5
6 2 4

输出

16

说明

Rabbit可以选择分别用1天，1天，3天完成这三个任务，最大满意度为6+6+4=16

备注:

2≤ N,K≤ 2000,K≤ W≤ min(4000,2*K) 0<vi≤ 10000

题解：

不难看出是一个背包问题
我们想想背包问题有几个要素：物品花费（本题中为天数），物品价值（本题为满意度），物品数量，总容积（本题为W天）。你会发现我没有标物品数量，那是因为在这个题里面物品只有总数量，也就是总任务数K，却没有单个物品的数量。这咋整，怎么才能把数量这个限制给去掉？
我们可以这么想，一共有K个任务，那我们先给每个任务分配一天，一共用掉K天，因为我们要求第W天正好完成，所以还剩下W-K天没有分配，而剩下这些天数可以随便分配，没有数量限制（因为一个任务最少要1天，而我们上来就给了每个任务一天，所以给分配时，无需考虑是否有任务没做）
无数个W-K天，不就成完全背包问题了吗？
注意给的满意度是指i天对应的满意值，而非第i天，所以我们要先处理一下，将每天的满意值减去第一天满意值（相当于第一天已分配）。
最后再加上即可

代码：

#include <bits/stdc++.h>
using namespace std;
int dp[4010], a[2010];
int main() 
{
   
    int n, k, w;//可用天数，任务数量，容量 
    scanf("%d %d %d", &n, &k, &w);
    memset(dp,-0x3f,sizeof(dp));
    dp[0] = 0;
    scanf("%d", &a[0]);
    for(int i = 1; i < n; i++) {
   
        scanf("%d", &a[i]);
        a[i] -= a[0];//与第一天的差 
    }
    w -= k;//
    for(int i = 1; i < n; i++) {
   //无穷背包 
        for(int j = i; j <= w; j++) {
   
      		dp[j] = max(dp[j-i] +a[i],dp[j]);
        }
    }
    printf("%d\n", dp[w]+k*a[0]);
    return 0;
}