区间dp 总结&详解
区间 dp の的定义
区间类动态规划是线性动态规划的扩展，它在分阶段地划分问题时，与阶段中元素出现的顺序和由
前一阶段的哪些元素合并而来有很大的关系。
令状态表示将下标位置
到
的所有元素合并能获得的价值的最大值，那么
，
为将这两组元素合并起来的代价。
(以上内容来自OI-WIKI)
模板
既然求一个区间的最优解，可以先把区间分割。我们用len枚举小区间的长度，j是区间的开头，end是结尾。然后再两端中间枚举分割点i。模板如下:
for(int len=1;len<=n;len++){//枚举长度
for(int j=1;j+len<=n+1;j++){//枚举起点
int end=j+len-1;
for(int i=j;i<end;i++)//枚举分割点
dp[j][end]=min(dp[j][end],dp[j][i]+dp[i+1][end]+w(j,end));
}
}线性的区间 dp
例题:P1775
Sol
这是一道很经典的题目的弱化版。读完题，我们知道，板子里的其实就是每次要合并的两堆的质量和。而这个，可以通过用前缀和维护来解决。
Code
#include <bits/stdc++.h>
using namespace std;
int dp[maxn][maxn],a[maxn],sum[maxn];
int main(){
int n;
cin>>n;
memset(dp,0x3f,sizeof(dp));
for(int i=1;i<=n;i++){
cin>>a[i];
sum[i]=sum[i-1]+a[i];
dp[i][i]=0;
}
for(int len=2;len<=n;len++){
for(int i=1;i<=n-len+1;i++){
int j=i+len-1;
for(int k=i;k<j;k++)
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);
}
}
cout<<dp[1][n]<<endl;
return 0;
}环形的区间 dp
例题:P1880
Sol
乍一看跟弱化版差不了多少。但是——请注意题目中这句话:在一个圆形操场的四周摆放 N 堆石子，所以说它是一个环形的。因此我们破环为链，把原数组复制一遍即可。
Code
#include <bits/stdc++.h>
using namespace std;
int a[maxn],dpmin[maxn][maxn],dpmax[maxn][maxn],sum[maxn];
int main(){
memset(dpmax,0,sizeof(dpmax));
[请填空]
int n;
cin>>n;
sum[0]=0;
for(int i=1;i<=n;i++){
cin>>a[i];
a[i+n]=a[i];
}
for(int i=1;i<2*n;i++){
sum[i]=sum[i-1]+a[i];
dpmin[i][i]=[请填空]=0;
}
for(int len=2;len<=n;len++){
for(int j=1;len+j-1<2*n;j++){
int end=len+j-1;
for(int i=j;i<end;i++){
dpmax[j][end]=max(dpmax[j][end],dpmax[j][i]+dpmax[i+1][end]+sum[end]-sum[j-1]);
[请填空]
}
}
}
int ansmin=0xfffffff;
int ansmax=-1;
for(int i=1;i<=n;i++){
ansmin=min(ansmin,dpmin[i][i+n-1]);
[请填空]
}
cout<<ansmin<<endl<<ansmax<<endl;
return 0;
}四边形不等式优化
如果你翻一翻P1880的题解就会发现，dalao们基本都是用四边形不等式做的。BUT对于我这种蒟蒻来说，四边形不等式优化实在是太难了！我也不会证，所以挂几个其他博客的地址。
思路
首先，我们得知道四边形不等式是什么。简单来说，就是当时，dp 的方程满足
就是一个四边形不等式。
令为
选的k,那:
且
所以，我们得出的范围:
。所以，我们枚举 k 的时候只需要在这个范围枚举了。顺便说一下，
。这样，就可以把时间复杂度降到
。
代码
P1775
#include <bits/stdc++.h>
using namespace std;
int a[maxn],sum[maxn];
int dp[maxn][maxn];
int s[maxn][maxn];
int main(){
int n;
cin>>n;
sum[0]=0;
memset(dp,0x3f,sizeof(dp));
for(int i=1;i<=n;i++){
cin>>a[i];
sum[i]=sum[i-1]+a[i];
dp[i][i]=0;
s[i][i]=i;
}
for(int len=2;len<=n;len++){
for(int j=1;j<=n;j++){
int end=j+len-1;
if(end>n)
continue;
for(int i=s[j][end-1];i<=s[j+1][end];i++){
if(dp[j][i]+dp[i+1][end]+sum[end]-sum[j-1]<dp[j][end]){
dp[j][end]=dp[j][i]+dp[i+1][end]+sum[end]-sum[j-1];
s[j][end]=i;
}
}
}
}
cout<<dp[1][n]<<endl;
return 0;
}P1880
注意:由于dpmax是不满足单调性，所以无法用四边形不等式优化。
#include <bits/stdc++.h>
using namespace std;
int dpmin[205][205];
int s[205][205];
int a[205],sum[205];
int main(){
int n;
cin>>n;
memset(dpmin,0x3f,sizeof(dpmin));
for(int i=1;i<=n;i++){
cin>>a[i];
dpmin[i][i]=0;
s[i][i]=i;
sum[i]=sum[i-1]+a[i];
}
for(int i=1;i<=n;i++){
sum[i+n]=sum[i+n-1]+a[i];
s[i+n][i+n]=i+n;
dpmin[i+n][i+n]=0;
}
for(int len=1;len<=n;len++){
for(int j=1;j+len<=2*n;j++){
int end=j+len-1;
for(int k=s[j][end-1];k<=s[j+1][end];k++){
if(dpmin[j][end]>dpmin[j][k]+dpmin[k+1][end]+sum[end]-sum[j-1]){
dpmin[j][end]=dpmin[j][k]+dpmin[k+1][end]+sum[end]-sum[j-1];
s[j][end]=k;
}
}
}
}
int ansmin=0xfffffff;
for(int i=1;i<=n;i++)
ansmin=min(ansmin,dpmin[i][i+n-1]);
cout<<ansmin<<endl;
return 0;
}友情提醒:请不要无脑Ctrl C+Ctrl V
原文地址：https://blog.csdn.net/seanli1008/article/details/142684625
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！