该题考察了完全背包
题目链接：https://ac.nowcoder.com/acm/problem/21186

感谢博客1：https://ac.nowcoder.com/acm/problem/blogs/21186
感谢博客2：https://blog.csdn.net/zygnewczh/article/details/107188919
当然更要感谢经典的：背包问题九讲

题目描述
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天 物品件数——N
物品费用——完成一个任务所需天数i 物品价值——满意度vi
最优解的同时要求背包容量装满——恰用W天完成
**然而题目多了一个要求：完成k个任务，也就是要求选择的物品总件数为k
所以我们当然想消除这个k的约束，从而愉快地直接套用完全背包（注意备注的范围`K≤ W≤ min(4000,2K)`暗示着些什么）
——————————————————————————————

1. 先给每个任务分配一天，也就是率先获得k个一天的满意度（保证完成了k个任务）
2. 差分算出其余天数与第一天的满意度，接着就是完全背包了~（剩余的天数也要完成任务，但这时没有k的约束了，可自由分配咯）
   此时的完全背包为：
   背包容量——W-k天 物品件数——N-1
   物品费用——完成一个任务所需天数i 物品价值——满意度vi-v0
   最优解的同时要求背包容量装满——恰用W-k天完成

***无其他约束条件
——————————————完整代码————————————————

#include <iostream>
#include <algorithm>

using namespace std;

int a[2005];
int dp[5005];
int main(){
	int n, k, W;
	scanf("%d%d%d", &n, &k, &W);
	scanf("%d", &a[0]);
	for(int i = 1; i < n; ++i){
		scanf("%d", &a[i]);
		a[i] = a[i] - a[0];//价值v[i]-v[0]
	}
	fill(dp+1, dp+k+1, -0x3f3f3f);//背包要求装满
	dp[0] = 0;
	W -= k;
	for(int i = 1; i < n; ++i){//完全背包
		for(int j = i; j <= W; ++j){
			dp[j] = max(dp[j], dp[j-i]+a[i]);
		}
	}
	printf("%d", dp[W]+a[0]*k);
	return 0;
}