该题题意为给定一个序列，这个序列能够按照栈的规则进行进出，只不过每个位置的数具有一个数值，每次用出来的顺序减1乘以这个数值，求最后的综合最小。
我们有这样的设想，对于一个序列 A B C ... Z，他们有相对应的数值 value[A], value[B] ... value[Z]，现在对整个串进行分析，我们试图分析能否找到该问题的子问题，设f[i][j] 为 i 到 j 这个序列能够出来的最小值，那么对于第i号元素来说，我们有如下选择，先出去若干个元素再让a出去，对于某一个区间，我们又可以细分下去。为什么要选择 i 号元素来考虑，因为我们考虑 i 号元素时，选择其他的元素段来考虑都将是一个连续的段落，这样就可以递归下去处理。
还有一个问题就是当每次计算[a,b]时，我们都是单独的考虑这一段，也就是说如果a,a+1号元素出队的话，那么数值统计就是 (1-1) * value[a] + (2-1) * value[b]; 对于任意一段递归下去的区间都是这样计算，那么这样可能又会有疑问了，如何保持题中所说的顺序了，技巧就是当[a, b]前有 1,2...a-1 元素已经出队了，那么整个数值要加上 sum(value[a...b]) * (a-1)。可以去计算一下。
代码如下：
#include <iostream> #include <cstdlib> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <string> #include <map> #include <queue> #include <vector> #include <stack> #include <list> #include <set> #define INF 0x3f3f3f3f #define MAXN 100 using namespace std; int N, s[MAXN+5], f[MAXN+5][MAXN+5], seq[MAXN+5]; int dfs(int x, int y) { if (f[x][y] != INF) { return f[x][y]; } else if (x >= y) return 0; for (int i = 0; i <= y-x ; ++i) { f[x][y] = min(f[x][y], dfs(x+1, x+i) + dfs(x+i+1, y) + (i+1)*(s[y]-s[x+i]) + i*seq[x]); } return f[x][y]; } int main() { int T, ca = 0; scanf("%d", &T); while (T--) { memset(f, 0x3f, sizeof (f)); scanf("%d", &N); for (int i = 1; i <= N; ++i) { scanf("%d", seq+i); s[i] = s[i-1] + seq[i]; } printf("Case #%d: %d\n", ++ca, dfs(1, N)); } return 0; }