本文共 1287 字，大约阅读时间需要 4 分钟。

n个人参加节目，每人都有一个自己的不高兴值

如果他第k个上场，那么他的不高兴值为(k−1) * a[i] 第 k 个等待的人不高兴值成 ( k - 1 ) * a[i]，有一个小黑屋可以暂时存放一些人，让他们晚点上台，进去的越早出来的越晚，但显然越晚，不高兴值越大，求最小的总不高兴值。

那么第i个人可以在第一个、第二个位置等等出场…直到j+i-1

我们用d[i][j]来存储第i个人到第j个人能得到的最小的不高兴值

假设第i个人的花费是k * a[i]，则它在这一区段中是第k+i个上场的(以i开始的)

那么就可以分两段，d[i+1][i+k−1]和d[i+k][j] 由于小黑屋的先进后出 所以排在i后面的i+k到j个人要先上，只需要原来的花费 而排在i前面的i+1到i+k-1要后上，所以花费要更多一些，即加上k * (sum[j]-sum[i+k-1])) //这一区段的a[i]值的和✖️k

最后转移方程为:

d[i][j] = min( d[i[j],d[i+1][i+k-1]+d[i+k][j]+a[i] *( k-1)+k * (sum[j]-sum[i+k-1]))

#include 
   
    #include 
    
     #include
     
      using namespace std;#define mann 0x3f3f3f3fint  a[105],sum[105];int d[105][105],n,t;int main(){    int s = 1;    cin >> t;    while( t-- )    {        cin >> n;        sum[0]=0;        memset(d,0,sizeof(d));        for(int i=1; i<=n; i++)        {            cin >> a[i];            sum[i] = sum[i-1]+a[i];//提前记录每一区段的花费的原值的总和，前缀和        }        for(int len=2; len<=n; len++)        {            for(int i=1,j = i+len-1; j<=n; i++,j++)            {                d[i][j] = mann;                for(int k=1; k<=len; k++)                {                    d[i][j] = min( d[i[j],d[i+1][i+k-1]+d[i+k][j]+a[i]*(k-1)+k*(sum[j]-sum[i+k-1]));                }            }        }        cout <<"Case #"<
      
       <<": " <
       
        <