概览
一堆位置固定顺序的石子,怎么合并才能代价最小
题解
f[i,j]: 所有起点为i,终点为j的方案的最小值
状态划分:
按照最后一步的位置进行划分
f[i,j] = min(f[i,j], f[i,k] + f[k+1,j]+s[i,j])
实际做的时候,关键是思考实际DP对应的有向图的实际走向,即依赖
f[1,1], f[1,2], f[1,3], …, f[1,n]
f[2,1], f[2,2],f[2,3],…, f[2,n]
目的顺序
f[1,n]->f[1,k], f[k+1,n]
f[i,j]->f[i,k],f[k+1,j]
发现实际的依赖顺序是长度,所以在循环时的想法是对长度做第一层循环,对起点做第二层循环(其实终点也可以,但是反套路)
代码
#include<iostream>
using namespace std;
const int N=310, INF=1e9;
int n;
int s[N]; // 前缀和
int f[N][N];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&s[i]);
for(int i=1;i<=n;i++) s[i] +=s[i-1];
// len=1, 不需要做什么
for(int len=2;len<=n;len++) // 长度
for(int i=1;i+len-1<=n;i++) // 起点
{ // i+len-1 终点不能超过边界
int l=i, r=i+len-1;
f[l][r]=INF; // 凡是求min, 记得初始化为一个大的数
for(int k=l;k<=r;k++)
f[l][r] = min(f[l][r], f[l][k]+f[k+1][r]+s[r]-s[l-1]);
}
printf("%d\n",f[1][n]);
return 0;
}
先枚举长度的解释好评!很多题解都没有写这个