SDNU 1045.石子合并1（区间dp）

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define eps 1e-9
#define pi acos(-1)

const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const int maxn = 1000 + 8;

int n, a[maxn], sum[maxn], dp[maxn][maxn];

int main()
{
    std::ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    sum[0] = 0;
    while(cin >> n)
    {
        memset(dp, 0, sizeof(dp));
        for(int i = 1; i <= n; i++)
        {
            cin >> a[i];
            sum[i] += a[i] + sum[i - 1];
        }
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j + i <= n; j++)
            {
                int en = j + i;
                int tmp = sum[en] - sum[j - 1];
                dp[j][en] = inf;
                for(int k = j; k < en; k++)
                    dp[j][en] = min(dp[j][en], dp[j][k] + dp[k + 1][en] + tmp);
            }
        }
        cout << dp[1][n] <<‘\n‘;
    }
    return 0;
}