洛谷 P1880 石子合并（区间DP）

原题链接：https://www.luogu.org/problem/P1880

区间DP很经典的一道题

花了好长时间才弄明白原理

区间DP把大区间转化成小区间来处理，然后对小区间处理后再回溯的求出大区间的值，主要的方法有两种，记忆化搜索和递推

附赠区间DP模板：

memset(dp,0,sizeof(dp))//初始dp数组
for(int len=2;len<=n;len++){//枚举区间长度
    for(int i=1;i<n;++i){//枚举区间的起点
        int j=i+len-1;//根据起点和长度得出终点
        if(j>n) break;//符合条件的终点
        for(int k=i;k<j;++k)//枚举最优分割点
            dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+w[i][j]);//状态转移方程
    }
}

原题代码：

#include <bits/stdc++.h>
using namespace std;
int a[250],d[250][250],p[250][250],sum[250];
void init()
{
    for(int i=0;i<210;i++)
    {
        for(int j=0;j<210;j++)
        {
            if(i==j)
            {d[i][j]=0;
            p[i][j]=0;}
            else
            {d[i][j]=99999999;
            p[i][j]=0;}
        }
    }
}
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {cin>>a[i];}
    int cnt=n;
    for(int i=0;i<n;i++)
    {a[cnt]=a[i];
    cnt++;}
    init();
    sum[0]=0,sum[1]=a[0];
    for(int i=2;i<=2*n;i++)
    {sum[i]=a[i-1]+sum[i-1];}
    int minn=99999999,maxx=-1;
    for(int len=2;len<=n;len++)
    {
        for(int i=0;i<2*n;i++)
        {
            int j=i+len-1;
            if(j>=2*n)
            {break;}
            for(int k=i;k<j;k++)
            {
                d[i][j]=min(d[i][j],d[i][k]+d[k+1][j]+sum[j+1]-sum[i]);
                p[i][j]=max(p[i][j],p[i][k]+p[k+1][j]+sum[j+1]-sum[i]);
            }
            if(len==n)
            {
                minn=min(minn,d[i][j]);
                maxx=max(maxx,p[i][j]);
            }
        }
    }
    cout<<minn<<'\n'<<maxx<<'\n';
    return 0;
}

123