区间dp的常用模板

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 310;
int f[N][N];
int main()
{
    for (int len=1;len<=n;len++) //先枚举区间长度
    {
        for (int i=1;i+len-1<=n;i++) //枚举左端点
        {
            int j=i+len-1; //右端点由左端点和区间长度即可确定
            if (len==1) f[i][j]==xxxxx;  //区间长度为1时的边界初始化
            for (int k=i;k<j;k++) // 枚举分割点
                f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]....); //构造状态转移方程
        }
    }
}

石子合并

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 310;
int f[N][N];
int n;
int a[N],s[N];
int main()
{
    cin>>n;
    for (int i=1;i<=n;i++)  //前缀和初始化
    {
        cin>>a[i];
        s[i]=s[i-1]+a[i];
    }

    memset(f,0x3f,sizeof f);
    for (int len=1;len<=n;len++)  //先枚举区间长度
    {
        for (int i=1;i+len-1<=n;i++) //再枚举起点即左端点
        {
            int j=i+len-1; //右端点由起点和区间长度就可确定
            if (len==1) f[i][j]=0; //区间长度为1时，表示左右端点相等，即将一堆石子聚堆的代价为0
            for (int k=i;k<j;k++) //枚举分割点
                f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]);
        }
    }
    cout<<f[1][n]<<endl; //答案就是将第1堆到第n堆聚起来的最小代价
    return 0;
}