牛客网
@[toc]

题目描述

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;
}