题面

法阵由从左至右 $n$ 道魔力屏障组成，每道屏障有一个临界值 $a_i$ ，如果它承受攻击的魔力值 $>a_i$ ，屏障将会破碎，它所承受的魔力攻击将在魔力值减半后（向下取整）继续向右移动，否则该攻击会被该屏障完全拦截，停留在屏障前，屏障的临界值不会减少。当两次攻击相遇时，两次攻击会叠加形成新的攻击，新的攻击的魔力值为两次攻击魔力值之和，新的攻击会继续向右移动。小 Z 可以在法阵中任意一个位置释放任意大小魔力值的攻击，攻击会向右移动直到遇到一个还未被摧毁的屏障或离开法阵。

对于所有 $1\leq i\leq n$ ，小 Z 希望用最小的法力值使得第 $1\sim i$ 道屏障全部破碎。

$n\leq70,a_i\leq150$ 。

题解

一开始设的是 $f_{i,j}$ 表示做完前 $i$ 个剩下 $j$ 的最小花费。然后转移时发现没办法维护哪些是跨过去的、哪些是和它一起攻击 $i$ 的。但是显然和 $i$ 一起攻击的一定是连续的一段，同时跨过去的也是连续的一段。那么区间 DP，设 $f_{l,r,j}$ 表示区间 $[l,r]$ 剩下 $j$ 的最小花费。转移先考虑整个区间都一起攻击。复杂度 $\mathcal{O}(n^3V^2)$ 其中 $V$ 表示值域。

代码

const int N = 100, M = 180;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	int n;
	int a[N], sum[N];
	int f[N][N][M], ans = 0x3f3f3f3f;
	int main () {
		n = Read();
		for (int i = 1; i <= n; i++) a[i] = Read(), sum[i] = sum[i - 1] + a[i];
		memset (f, 0x3f3f3f3f, sizeof f);
		for (int i = 1; i <= n; i++) 
			for (int j = a[i]; j <= M - 30; j++)
				f[i][i][j / 2] = min(f[i][i][j / 2], j);
		for (int len = 2; len <= n; len++) {
			for (int l = 1, r; (r = l + len - 1) <= n; l++) {
				for (int k1 = 0; k1 <= M - 30; k1++)
					for (int k2 = max(a[r] - k1, 0); k2 <= M - 30; k2++)
						f[l][r][(k1 + k2) / 2] = min(f[l][r][(k1 + k2) / 2], f[l][r - 1][k1] + k2);
				for (int k = l; k < r; k++) {
					for (int k1 = 0; k1 <= M - 30; k1++) {
						for (int k2 = 0; k2 <= M - 30; k2++)
							f[l][r][k1 + k2] = min(f[l][r][k1+k2],f[l][k][k1] + f[k + 1][r][k2]);
					}
				}
			}
		}
		for (int r = 1; r <= n; printf ("%d%c", ans, r==n?'\n':' '), ans = 0x3f3f3f3f, r++)
			for (int k = 0; k <= M - 30; k++) ans = min(ans, f[1][r][k]);
		return 0;
	}
}

int main () {
	freopen("magic.in", "r", stdin);
	freopen("magic.out", "w", stdout);
	Main::main();
	return 0;
}