Teamwork (USACO Gold 2018 December)

$N=10^4$ ，再加求序列上某些值的和的最大值，看起来就是个DP。实际上也的确是个比较标准的DP题。

定义状态 $\text{dp}[i][j]$ ：前 $i$ 头牛，最后一个小组大小为 $j$ 的情况下的最大值。状态转移的过程中，我们需要跟踪最后一段序列的最大值（ $\text{smax}[]$ ）。

最后复杂度是 $\mathcal{O}(NK)$ 。

这个题的设定，和Snakes比较类似。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int n, K;
int a[10005];
int dp[10005][1005];    // dp[i][j], best total after i cows, with last team size j
int smax[1005];         // smax[i]: max skill of postfix of length i
int ans;
 
int main() {
    scanf("%d %d", &n, &K);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    
    int best = 0;
    for (int i = 1; i <= n; i++) {
        dp[i][1] = best + a[i];     // start a new team
        best = dp[i][1];
        for (int j = 2; j <= min(i, K); j++) {
            // enlarge last team
            dp[i][j] = dp[i-1][j-1] + (a[i] > smax[j-1] ? a[i] + (a[i]-smax[j-1])*(j-1) : smax[j-1]);
            best = max(best, dp[i][j]);
        }
        for (int j = min(i, K); j >= 1; j--) {
            // update smax
            smax[j] = max(smax[j-1], a[i]); 
            // answer
            if (i == n)
                ans = max(ans, dp[i][j]);
        }
    }
    printf("%d", ans);
    return 0;
}