题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=4283

解题思路

dp[i][j]表示假如只有j-i+1个人，分别为i，i+1，……，j，这j-i+1个人进入小黑屋的愤怒值之和。
对于区间[i,j]，每次只考虑第i个人的位置，那么他上场的顺序为第1个~第j-i+1个，设位置为k（k=i+上场顺序），这时，这个区间就被分为了两段， [i+1,k]和[k+1,j]。
如何转移呢？
让第i个人去第k个位置，也就是第（k-i+1）个上场，这样一来，就得把[i+1,k]所有的人前移一位，[k+1,j]无需动。
转移方程：dp[i][j]=min{第i+1到第k个人先上场的愤怒值+第i个人在第k个位置（[1,n]区间而言的k，与上面的k一个含义）上场的愤怒值+第k+1到第j个人最后上场的愤怒值}
转化为代码：
第i+1到第k个人先上场的愤怒值=dp[i+1][k]就是dp本身的含义嘛
第i个人在第k个位置上场的愤怒值=angry[i]*在这j-i+1个人中的位置=angry[i]*(k-i)
第k+1到第j个人最后上场的愤怒值=第k+1个人在这j-i+1个人中第k-i+1个上场，第k+2个人在这j-i+1个人中第k-i+2个上场……=第k+1到第j个人最先上场的愤怒值+偏移k-i+1个位置的怒气增量=dp[k+1][j]+(k-i+1)*(sum[j]-sum[k])
综上，转移方程： dp[i][j]=min(dp[i][j],dp[i+1][k]+(k-i)*a[i]+dp[k+1][j]+(k-i+1)*(sum[j]-sum[k]))

AC代码

#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=110;
int dp[N][N],sum[N],a[N],n,T;
int main(){
    cin>>T;
    for(int t=1;t<=T;t++){
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i],sum[i]=sum[i-1]+a[i],dp[i][i]=0;
        for(int len=2;len<=n;len++)
            for(int i=1;i+len-1<=n;i++){
                int j=len+i-1;
                dp[i][j]=inf;
                for(int k=i;k<=j;k++)
                    dp[i][j]=min(dp[i][j],dp[i+1][k]+(k-i)*a[i]+dp[k+1][j]+(k-i+1)*(sum[j]-sum[k]));
            }
        printf("Case #%d: %d\n",t,dp[1][n]);
    }
}