[bzoj 4897] [Thu Summer Camp2016]成绩单

一个长度为n的序列w, 每次删掉连续的一段, 最后被删光. 一个删除方案的代价: 是删除的次数 (无限制), 是第i次删掉的那段的最大值, 是最小值, 是给定的参数. 求最小代价. (n≤50, a≤100, b≤10, wi≤300) 阅读了一些dalao的游记, 已知: 这题是个复杂度的DP, bzoj 2121 与之类似.

也许想定义状态 g[i][j] 为删光[i,j]的最小代价, 做一个区间DP, 枚举一下分割点. 这样不可行, 因为两个子问题不是相互独立的. 需要修改/扩充状态表示.

可以借鉴 bzoj 2121. 定义 f[i][j][l][r] 为删掉[i,j]的一些子段, 剩余部分最小值为l, 最大值为r (需要离散化) 的最小代价. 考虑w[j]是否在剩余部分内: - w[j]在剩余部分内, 被删掉的子段都在[i,j-1]内, 用某些 f[i][j-1][*][*] 来更新. - w[j]被删掉了, 枚举剩余部分的右端点(k-1), 用 f[i][k-1][l][r] + g[k][j] 来更新.

同时, g[i][j] = min { f[i][j][l][r] }.

边界: f[i][i][w[i]][w[i]] = 0, g[i][i] = a, 其余量初始化为inf.

注意递推的顺序. 可以逆序枚举i, 其余三维顺序枚举.

这道题有一些新颖之处. 矩阵链乘法这样的区间DP中, 我们考虑的是第一次分割. 而本题中, 我们考虑的是最后一次删除.

const int N = 50, inf = (1<<30)-1;

template<typename T>
inline void upmax(T& x, T v)
{
	x = max(x, v);
}

template<typename T>
inline void upmin(T& x, T v)
{
	x = min(x, v);
}

int top, w[N], H[N], f[N][N][N][N], g[N][N];

int main()
{
	int n, a, b;
	scanf("%d%d%d", &n, &a, &b);
	rep (i, 0, n) {
		scanf("%d", w+i);
		H[top++] = w[i];
	}
	sort(H, H+top);
	top = unique(H, H+top) - H;
	rep (i, 0, n)
		w[i] = lower_bound(H, H+top, w[i]) - H;
	
	fill_n(***f, sizeof(f)/sizeof(int), inf);
	fill_n(*g, sizeof(g)/sizeof(int), inf);
	
	per (i, n-1, 0) {
		int mn = w[i], mx = w[i];
		
		f[i][i][mn][mx] = 0;
		g[i][i] = a;
		
		rep (j, i+1, n) {
			upmin(mn, w[j]);
			upmax(mx, w[j]);
			
			rep (l, mn, mx+1) rep (r, l, mx+1) {
				int& now = f[i][j][l][r];

				if (w[j] >= l && w[j] <= r)
					upmin(now, f[i][j-1][l][r]);
				if (w[j] == r)
					rep (m, l, r)
						upmin(now, f[i][j-1][l][m]);
				if (w[j] == l)
					rep (m, l+1, r+1)
						upmin(now, f[i][j-1][m][r]);

				per (k, j, i+1) {
					if (f[i][k-1][l][r] == inf) break;
					upmin(now, f[i][k-1][l][r] + g[k][j]);
				}

				if (f[i][j][l][r] < inf)
					upmin(g[i][j], f[i][j][l][r] + a + b * (H[r]-H[l]) * (H[r]-H[l]));
			}
		}
	}

	printf("%d\n", g[0][n-1]);

	return 0;
}