Gold: Teamwork G

Usaco.guide 上的 normal，但感觉比很多 easy还简单：P5124 USACO18DEC] Teamwork G

总体来说是线性dp

设定状态

dp[i]=ans\ until\ i

这里的​dp[i]就是直到第​i头牛的答案

状态转移

对于​dp[i]来说，考虑上一步的答案到当前​i是怎么转移的。上一步的区间其实就是​i-k+1一直到​i。所以这当中选择一个最大的答案。根据题意，答案就是​maxskill*number。所以考虑从​i往前遍历，过程中更新​maxskill， 然后 max一下答案就好了：

maxskill=max(maxskill,skill[j-1])\\ dp[i]=max(dp[i],dp[j-1]+maxskill*(i-j+1))
  • ​dp[j-1]就是上一步答案
  • ​i-j+1就是当前遍历是按几个牛一组算的
  • ​skill[j-1]而不是​j是因为我需要​dp[j-1]作为上一步答案，也就是说我这里的​j和原数组是偏移1的

代码

//
// Created by Chixiyu on 2/7/2024.
//
#include <bits/stdc++.h>
using namespace std;

const int N = 1e4 + 10;
int skills[N];
int dp[N];

int main() {
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; ++i) {
        cin >> skills[i];
    }
    for (int i = 1; i <= n; ++i) {
        int maxskill = 0;
        for (int j = i; j > 0 && i - j+1 <= k; --j) {
            maxskill = max(maxskill, skills[j-1]);
            dp[i] = max(dp[i], dp[j-1]+maxskill*(i-j+1));
        }
    }
    cout << dp[n] << endl;
    return 0;
}