题意

有一个队列，每个人有一个愤怒值D，如果他是第K个上场，不开心指数就为(K-1)*D。但是边上有一个小黑屋（一个FILO堆栈），可以一定程度上调整上场程序，求一种安排上场方案使得所有人的不开心指数和最小。

思路

非常好的一道区间DP题，涨了姿势了^.^ 这道题困扰我的地方就在于怎么处理进堆出堆的那些情况，最后没办法网上看了题解，才想起这样一个美妙的性质：

进栈出栈满足括号匹配性质！ 关于括号匹配性质（即括号定理）是《算法导论》在深度优先搜索中讨论到的性质，实际上因为深度优先搜索就是栈的应用所以进出栈就满足括号定理。

---

 

括号定理：（我们用进出栈的方式描述）

设d[i]、d[j]表示第i和第j个元素的进栈时间，f[i]、f[j]表示第i和第j个元素的出栈时间，则下面三种情况有且仅有一种发生：

①区间[ d[i] ,  f[i] ]和[ d[j] ,  f[j] ]完全不相交，即 () () 这种情况；

②区间[ d[i] ,  f[i] ]完全包含[ d[j] ,  f[j] ]，此时表示i比j先进栈，即 ( () ) 这种情况；

③区间[ d[i] ,  f[i] ]完全包含于[ d[j] ,  f[j] ]，此时表示j比i先进栈，也是 ( () ) 这种情况；

---

  所以这里我们就发现其实这是一道区间DP： 我们设dp[i][j]表示从第i个人到第j个人这段区间的最小花费（只考虑这j-i+1个人，不需要考虑前面有多少人）。那么对于dp[i][j]的第i个人，就有可能第1个上场，也可以最后上场。考虑第k个上场，即在i+1之后的k-1个人是率先上场的，那么就出现了一个子问题 dp[i+1][k]表示在第i个人之前上场的；对于第i个人，由于是第k个上场的，那么愤怒值便是val[i]*(k-1)；其余的人是排在第k+1个之后出场的，也就是一个子问题dp[k+1][j]，对于这个区间的人，由于排在第k+1个之后，所以整体愤怒值要加上k*( sigma(val[k+1...j]) )

代码

  [cpp] #include <iostream> #include <cstdio> #include <cmath> #include <algorithm> #include <string> #include <cstring> #include <vector> #include <set> #include <stack> #include <queue> #define MID(x,y) ((x+y)/2) #define MEM(a,b) memset(a,b,sizeof(a)) #define REP(i, begin, end) for (int i = begin; i <= end; i ++) using namespace std; int dp[105][105], D[105], sum[105]; int main(){ int t; scanf("%d", &t); for (int ca = 1; ca <= t; ca ++){ int n; scanf("%d", &n); sum[0] = 0; for (int i = 0; i <= n; i ++){ for (int j = 0; j <= n; j ++){ if (j <= i) dp[i][j] = 0; else dp[i][j] = 0x3fffffff; } } for (int i = 1; i <= n; i ++){ scanf("%d", &D[i]); sum[i] = sum[i-1] + D[i]; } for (int len = 1; len < n; ++ len){ for (int i = 1; i + len <= n; i ++){ int j = i + len; for (int k = i; k <= j; k ++){ dp[i][j] = min(dp[i][j], dp[i+1][k]+(k-i)*D[i]+dp[k+1][j]+(k-i+1)*(sum[j]-sum[k])); } } } printf("Case #%d: %d\n", ca, dp[1][n]); } return 0; } [/cpp]