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\n", lhjakioi, dp[1][n]); // printf ("%d\n", dp[1][n]); } return 0; }

Conclusion

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

转载于:https://www.cnblogs.com/ChiTongZ/p/11368631.html