Rabbit的工作(2)

题目描述

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获得的总满意度最大是多少。

输入

3 3 5
6 2 4

输出

说明

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

备注:

2≤ N,K≤ 2000,K≤ W≤ min(4000,2*K)

0<vi≤ 10000

#include<bits/stdc++.h>
using namespace std;
const int N = 4e3 + 7;
int dp[N], v[N], n, k, w;
int main() {
    cin >> n >> k >> w;
    memset(dp, 0xcf, sizeof(dp));
    for (int i = 0; i < n; i++) cin >> v[i];
    for (int i = 1; i < n; i++) v[i] -= v[0];
    w -= k;
    dp[0] = 0;
    for (int i = 1; i < n; i++) {
        for (int j = i; j <= w; j++) {
            dp[j] = max(dp[j], dp[j - i] + v[i]);
        }
    }
    cout << dp[w] + k * v[0] << endl;
    return 0;
}

原文链接: https://www.cnblogs.com/HighLights/p/13322957.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/367107

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

Rabbit的工作(2)

题目描述

输入描述:

输出描述:

输入

输出

说明

备注:

相关推荐