1.关键是每个人都要进过栈
状态定义f[i,j]:[i,j]人之间最小的生气值
2.此题的区间分割点k的含义:左端点i第k个出栈
那么f[i + 1][i + k - 1] 代表在k之前出栈的数
加上第i个数向后偏移k - 1位 (k - 1) * w[i]
加上 k之后到j的数 此时状态已经_**确定**_ 在k之后出栈
那么要加上这段队伍的向后偏移k的生气值 k * (sum[j] - sum[i + k - 1])
得出转移方程:
f[i][j] = min(f[i][j], f[i + 1][i + k - 1] + (k - 1) * w[i]
+ f[i + k][j] + k* (sum[j] - sum[i + k - 1]);

代码:
#include<bits/stdc++.h>
using namespace std;
int f[110][110];
int w[110], s[110];
int INF = 0x3f3f3f3f;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;
    for(int cnt = 1;cnt <= t;cnt++)
    {
        memset(f, 0, sizeof f);
        int n;
        cin >> n;
        for(int i = 1;i <= n;i++)
        {
            cin >> w[i];
            s[i] = s[i - 1] + w[i];
        }

        for(int i = 1;i <= n;i++)f[i][i] = 0;

        for(int len = 2;len <= n;len++)
        {
            for(int i = 1;i + len - 1 <= n;i++)
            {
                int j = i + len - 1;
                f[i][j] = INF;

                for(int k = 1;k <= len;k++)
                {
                    f[i][j] = min(f[i][j], f[i + 1][i + k - 1] + w[i] * (k - 1) + f[i + k][j] + k * (s[j] - s[i + k - 1]));
                }
            }
        }
        cout << "Case #" << cnt << ": " << f[1][n] << endl;
    }
}