题目描述
为什么枚举两个顶点不行?
因为算f[i][j] 使会用到 f[i ~ j][j] 和 f[i][i ~ j]
例如 f[1][3] 会用到 f[1][1], f[1][2], f[2][3], f[3][3]
而先枚举i 再枚举j 会导致 f[2][3] f[3][3]未被计算
我的解决办法是先枚举j再枚举 i 逆序求 f[i][j]
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 310;
int f[N][N];
int a[N];
int n;
int main()
{
cin >> n;
for(int i = 1; i <= n; i ++)
{
cin >> a[i];
a[i] = a[i-1] + a[i];
}
for(int j = 1; j <= n; j ++)
{
for(int i = j - 1; i >= 1; i --)
{
f[i][j] = 1e9;
for(int k = i; k <= j; k ++)
{
f[i][j] = min(f[i][j], f[i][k] + f[k+1][j] + a[j] - a[i-1]);
}
}
}
cout << f[1][n] << endl;
return 0;
}