HDU4283:You Are the One

Pre

准备 (PPT) 的时候遇到的有一点神奇的题目。

直接看题解，不然 (PPT) 做不完。

Solution

考虑 (dp[i][j]) 表示区间 ([i,j]) 的答案，难在设计方程。

可以考虑第 (i) 个人什么时候出栈，假设为 (k) ，那么一定是它之后连着的 (k) 个人出栈，不能有后面的，否则不合法。

如果是大于 (j-i+1) 个出栈的，留到后面再计算。

所以就可以 (DP) 了。

Code

#include <cstdio>
#include <limits.h>
#include <algorithm>
using namespace std;
const int N = 100 + 5;
int dp[N][N], ans, n, sum[N];
int main () {
	int t;
	scanf ("%d", &t);
	for (int lhjakioi = 1; lhjakioi <= t; lhjakioi++) {
		scanf ("%d", &n);
		for (int i = 1; i <= n; ++i) {
			scanf ("%d", &sum[i]);
			sum[i] += sum[i - 1];
		}
		for (int i = 1; i <= n; ++i) {
			for (int j = 1; j <= n; ++j) {
				int u = j, v = j + i - 1;
				dp[u][v] = INT_MAX;
				if (v > n) continue;
				for (int k = 1; k <= i; ++k) {
					dp[u][v] = min (dp[u][v], dp[u + 1][u + k - 1] + (sum[u] - sum[u - 1]) * (k - 1) + dp[u + k][v] + (sum[v] - sum[u + k - 1]) * k);
				}
			}
		}
		printf ("Case #%d: %d
", lhjakioi, dp[1][n]);
//		printf ("%d
", dp[1][n]);
	}
	return 0;
}

Conclusion

这道题可以放到 (PPT) 上面来分享凑时间