Snakes (USACO Gold 2019 US Open)

这个是个挺标准的DP题。

定义 $dp[i][j][k]$ : $i$ 组蛇之后，改变了 $j$ 次网的大小，上一次改变网大小到 $i$ 的距离是 $k$ 的情况下，最少的浪费空间。然后用 $amax[i]$ 来记录最佳方案下，第 $i$ 段的网大小。然后DP状态转移也是比较直观的。

这个题和2018年12月USACO Gold的Teamwork比较类似。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int n, K;
int a[405];
int dp[405][405][405];      // dp[i][j][k]: best answer after i groups and j changes, length after last change is k
int amax[405];              // amax[i]: max of last i groups
int ans = INT32_MAX;
 
int main() {
    scanf("%d %d", &n, &K);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    memset(dp, 0x3f, sizeof(dp));
    dp[1][0][1] = 0;
    amax[1] = a[1];
    int best[405];
    memset(best, 0x3f, sizeof(best));
    best[0] = 0;
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j <= K; j++)
            dp[i][j][1] = best[j-1];            // do a change
        for (int j = 0; j <= K; j++) {
            best[j] = dp[i][j][1];
            if (i == n)
                ans = min(ans, dp[i][j][1]);
            for (int k = 2; k <= i-j; k++) {    // no change
                if (a[i] > amax[k-1])           // a[i] raises the net size
                    dp[i][j][k] = dp[i-1][j][k-1] + (a[i] - amax[k-1]) * (k-1);
                else
                    dp[i][j][k] = dp[i-1][j][k-1] + (amax[k-1] - a[i]);
                best[j] = min(best[j], dp[i][j][k]);
                if (i == n)
                    ans = min(ans, dp[i][j][k]);
            }
        }
        for (int k = i; k >= 1; k--) {          // update amax
            amax[k] = max(amax[k-1], a[i]);
        }
    }
    printf("%d\n", ans);
    return 0;
}