题意：有n个人准备按顺序上台，上台前有个小黑屋（先进后出，即栈），可以被安排进去等待，也可以直接上台，一个人一旦被安排进去，后面的人就可以先上台（小黑屋无限大）。每个人有一个愤怒值angry，如果他是第k个上台的，那么他的怒气和就是(k-1)*angry，如何运用小黑屋安排上台顺序，使得这n个人的怒气总和最小。
思路：这是一道区间dp题（这几天做的都是区间dp的专题，不是就见鬼了），状态很容易想到，用f[l][r]，表示l~r这r-l+1个人的最小怒气总和，那么如何转移，其实区间dp大概的套路也就是三个for( for len ; for l,r ; for k (l,r) )，而这题其中的小细节也比较容易观察到，那么问题来了，这也是为什么这题区间dp拿来写的原因，一般的k枚举都是l到r来划分区间，但是这题显然没有什么用，为什么没用？因为要用小黑屋啊！如果直接枚举断点，而这题的l, r点是没什么关系的（如果真的有，个人感觉也很难推出，因为每个人的出场顺序其实是不一定的），怎么算出最优？（不用小黑屋也可以看做进去马上出来，问题不大），那么考虑到一个问题，既然出场顺序不一定，那k就枚举出场顺序吧，显然区间l~r的一个人出场顺序就只有r-l+1种，因为如果只有len个人，怎么做到第len+1出场？（一场跑步比赛，你超越了最后一名，你是第几！），至此，转移的for考虑完了，那么这个k来枚举谁呢？第一个？最后一个？随便一个？其实，随便一个都可以，因为最后区间最优，其实顺序是定的，所以先枚举谁都可以，那么就枚举这个区间的第一个吧，因为好写。可以想想，第一个人第k个出场，是不是1~1+k-1比他早出场，1+k~end在他后面出场（所以这些人都多等待了k个人，因而怒气值要多加上k次），那么转移式子就出来了。
for套路有意思，k是来枚举顺序的，和别的区间dp（目前自己做到的）不太一样，就放了上来。 Codes：
#include#define pb push_back#define de(x) cout << #x << " = " << x << endl#define clr(a,b) memset(a,b,sizeof(a))using namespace std;typedef long long ll;const int INF = 0x3f3f3f3f;const int N = 110;int f[N][N];int a[N], pr[N];int main(){ int n; int cas = 1; int t; scanf("%d", &t); while ( t -- ) { scanf("%d", &n); pr[0] = 0; for ( int i = 1; i <= n; i ++ ) { scanf("%d", &a[i]); pr[i] = pr[i-1] + a[i]; f[i][i] = 0; } for ( int len = 2; len <= n; len ++ ) { for ( int l = 1, r; ( r = l + len - 1 ) <= n; l ++ ) { f[l][r] = INF; for ( int k = 1; k <= len; k ++ ) { f[l][r] = min( f[l][r], (k-1)*a[l] + f[l+1][l+k-1] + f[l+k][r] + k*(pr[r]-pr[l+k-1]) ); } } } printf("Case #%d: %d\n", cas++, f[1][n]); } return 0;}