原题链接: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