Rabbit的工作(2)【牛客练习赛36_C + dp背包】

题目链接

那么的巧合，竟是这题的原题

就是，我们既然一定要选取K个任务，就先去取K个任务，然后逐一加上需要的额外天数即可。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
#define INF 40000007
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int maxN = 4005;
int N, K, W, dp[maxN], a[maxN];
void init()
{
    for(int i=0; i<=W; i++) dp[i] = -INF;
}
int main()
{
    while(scanf("%d%d%d", &N, &K, &W)!=EOF)
    {
        init();
        for(int i=0; i<N; i++)
        {
            scanf("%d", &a[i]);
        }
        dp[K] = K * a[0];
        for(int i=1; i<N; i++) a[i] -= a[0];
        for(int i=K+1; i<=W; i++)
        {
            for(int j=1; j<min(N, i - K + 1); j++)
            {
                dp[i] = max(dp[i], dp[i-j] + a[j]);
            }
        }
        printf("%d\n", dp[W]);
    }
    return 0;
}