P5336 [THUSC2016] 成绩单
考虑这个题， 他是随机抽一段， 然后剩下的又拼起来， 这不符合常规的区间DP。 因为他出现这样一种情况， 一段数中被扣出若干段， 剩下若干段。 如图：
红色的是被取出的， 黑色的是留下的， 考虑我们的 DP 需要包含这样的一个状态， 考虑这道题比较特殊， 虽然剩下的黑色段是散的， 我们不关心他什么样， 只需要知道 \(max\) 和 \(min\) 即可， 所以设状态 \(g[l][r][mn][mx]\) 表示区间 \([l, r]\) 扣掉若干块， 剩下的段的 \(min = mn\)， \(max = mx\) 的最小代价。 我们的答案是全部取完， 设 \(f[l][r]\) 表示把区间 \([l, r]\) 全部取完的最小代价。 那么显然有：
$f[l][r] = max { g[1][n] + a + b \times (mx - mn)^2 } $。
\(g\) 的转移怎么想， 我们可以将状态分类， 上图的状态我们可以分为两类， 最后为为红色颜色段或者黑色颜色段两类， 这样我们 \(g[l][r][][]\)， 就可以这么转移， 但是我们不好取一整段颜色段。 等价地：
- \(g[l][r][][]\) 可以推到 \(g[l][r + 1][][]\)， 表示将 \(r + 1\) 归为黑色段。
- \(g[l][r][][]\)， 可以枚举一个 \(k\)， 由 \(g[l][k][][]\) 和 \(f[k + 1][r]\) 推过来， 相当于枚举红色段。
这样推过来就维护了所有的上图的状态。 问题就解决了。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N = 55;
int n, a, b, w[N], rw[N], g[N][N][N][N], f[N][N];
void chmin(int &x, int y) { x = min(x, y); }
void chmax(int &x, int y) { x = max(x, y); }
int main() {
scanf("%d%d%d", &n, &a, &b);
for(int i = 1; i <= n; i++)
scanf("%d", &w[i]), rw[i] = w[i];
sort(rw + 1, rw + 1 + n);
int cnt = unique(rw + 1, rw + 1 + n) - rw - 1;
for(int i = 1; i <= n; i++)
w[i] = lower_bound(rw + 1, rw + 1 + cnt, w[i]) - rw;
memset(f, 0x3f, sizeof f);
memset(g, 0x3f, sizeof g);
for(int i = 1; i <= n; i++) g[i][i][w[i]][w[i]] = 0;
for(int len = 1; len <= n; len++) {
for(int l = 1; l + len - 1 <= n; l++) {
int r = l + len - 1;
for(int mn = 1; mn <= cnt; mn++) {
for(int mx = mn; mx <= cnt; mx++) {
for(int k = l; k < r; k++)
chmin(g[l][r][mn][mx], g[l][k][mn][mx] + f[k + 1][r]);
if(r < n) chmin(g[l][r + 1][min(w[r + 1], mn)][max(w[r + 1], mx)], g[l][r][mn][mx]);
chmin(f[l][r], g[l][r][mn][mx] + a + b * (rw[mx] - rw[mn]) * (rw[mx] - rw[mn]));
}
}
}
}
printf("%d", f[1][n]);
return 0;
}