区间DP
对一段连续的区间进行动态规划，使其达到预期
特点
合并：即将两个或多个部分进行整合，当然也可以反过来；
特征：能将问题分解为能两两合并的形式；
求解：对整个问题设最优值，枚举合并点，将问题分解为左右两个部分，最后合并两个部分的最优值得到原问题的最优值。
特别——链变环
对于原区间是链，不能计算从后到前的问题，最常用法是把链后接链，变成相对的环；如1，2，-，n，1，2，-，n；
例题
https://www.luogu.com.cn/problem/P1880
令 f(i,j) 表示将区间 [i,j] 内的所有石子合并到一起的最大得分。
状态转移方程： f(i,j)=max(min){f(i,k)+f(k+1,j)+sum[j]-sum[i-1] }。sum_i 表示 a 数组的前缀和
先对区间长度len枚举(2<=len<=n);
然后枚举区间左端点i(2<=i<=2*n-len),同时得出右端点j;
最后枚举合并点k(i<=k<j);
Code
点击查看代码
const int maxn = 2e5 + 10;
int n, a[110];
int sum[210], fmx[210][210], fmn[210][210];
void solve() {
cin >> n;
memset(fmn, MAXN, sizeof(fmn));
for (int i = 1; i <= n; i++) {
cin >> a[i];
sum[i] = sum[i - 1] + a[i];
fmn[i][i] = 0;
}
for (int i = 1; i < n; i++) {
sum[i + n] = sum[i + n - 1] + a[i];
fmn[i + n][i + n] = 0;
}
int mx = 0, mn = MAXN;
for (int len = 2; len <= n; len++) {
for (int i = 1; i <= 2 * n - len; i++) {
int j = i + len - 1;
for (int k = i; k < j; k++) {
fmx[i][j] = max(fmx[i][j], fmx[i][k] + fmx[k + 1][j] + sum[j] - sum[i - 1]);
fmn[i][j] = min(fmn[i][j], fmn[i][k] + fmn[k + 1][j] + sum[j] - sum[i - 1]);
}
}
if (len == n) {
for (int i = 1; i <= n; i++) {
mx = max(mx, fmx[i][i + n - 1]);
mn = min(mn, fmn[i][i + n - 1]);
}
}
}
cout << mn << '\n' << mx;
}
细节
小优化：变环后的链只用到n-1就行；
对于求最小的结果，需要预先对fmn赋一个MAXN，再对每一个fmn[i][i]赋0：合并自身不需代价
标签：210,int,sum,fmn,枚举,区间,DP From： https://www.cnblogs.com/uanQ/p/18280288