题意

T组测试数据，每组输入N，表示有N个人要上台表演，然后输入这N个人的不开心度。如果第i个人第k个上台表演，那么他的不开心度就是d[i]*(k-1)。现在有一个狭窄的小黑屋，导演可以暂时让人先进入小黑屋中，然后让后面的人去舞台表演，因为小黑屋很狭窄所以最先进去的人最后才能出来，问怎么安排才能使所有人的不开心度最小，输出这个不开心度。

思路

$dp[i][j]$dp[i][j]表示区间[i,j]的最优解
假设第i个人第k个上台表演，那么他的不开心值就是(k-1)*a[i]
i 前面的那些人[i+1,i+k-1]表演顺序就是一个子问题
i 后面的那些人[i+k,j]表演顺序也是一个子问题，但是这些人前面有k个人表演,所以他们总的不开心值需要加上
$k * ([i+k,j]这些人的不开心之和)$k∗([i+k,j]这些人的不开心之和)
所以状态转移方程为：
$dp[i][j] = min(dp[i + 1][i + k - 1] + dp[i + k][j] + (k - 1) * a[i] + k * (sum[j] - sum[i + k - 1]))，1≤k≤j-i+1$dp[i][j]=min(dp[i+1][i+k−1]+dp[i+k][j]+(k−1)∗a[i]+k∗(sum[j]−sum[i+k−1]))，1≤k≤j−i+1
显然只有$dp[i][i]$dp[i][i]初始为0，其他位置为INF

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 105;
const int INF = 0x3f3f3f3f;
int n, a[MAXN], sum[MAXN], dp[MAXN][MAXN];
int main()
{
    int T, CASE = 1; scanf("%d", &T);
    while (T--)
    {
        scanf("%d", &n);
        for (int i = 0; i < n; i++) scanf("%d", &a[i]);
        sum[0] = a[0];
        for (int i = 1; i < n; i++) sum[i] = sum[i - 1] + a[i];
        memset(dp, 0, sizeof(dp));
        for (int len = 2; len <= n; len++)
        {
            for (int i = 0; i + len - 1 < n; i++)
            {
                int j = i + len - 1;
                dp[i][j] = INF;
                for (int k = 1; k <= len; k++)
                {
                    dp[i][j] = min(dp[i][j], dp[i + 1][i + k - 1] + dp[i + k][j] + (k - 1) * a[i] + k * (sum[j] - sum[i + k - 1]));
                }
            }
        }
        printf("Case #%d: %d\n", CASE++, dp[0][n - 1]);
    }
    return 0;
}
/*
2　
5
1 2 3 4 5
5
5 4 3 2 2
*/