区间DP
一般的枚举方法:先枚举区间,再枚举左端点
石子合并
1. 状态表示f[i][j]
集合:i~j的合并方案
属性:min代价最小
2. 状态转换
f[i][j]分为以k = i,i+1,i+2…j-1为界(具体看代码)
code
#include<iostream>
using namespace std;
const int N = 310;
int n;
int s[N], f[N][N];
int main()
{
cin >> n;
for(int i = 0; i < n; ++i) {
cin >> s[i];
if(i - 1 >= 0) s[i] += s[i - 1];
}
//1 区间问题通用做法:先枚举区间长度,再枚举区间起点
for(int len = 2; len <= n; ++len){
for(int i = 0; i + len - 1 < n; ++i){
int j = i + len - 1;
//2 如何取值? 哦,y总说非常大的数qwq,那就1e9吧
f[i][j] = 1e9;
for(int k = i; k < j; ++k){
f[i][j] = min(f[i][k] + f[k + 1][j] + s[j] - s[i - 1], f[i][j]);
}
}
}
cout << f[0][n - 1] << endl;
}