先看一下模板
点击查看代码
//f[i][j]表示从i到j区间的值
for(int len=2;len<=n;len++)//len表示区间长度
{
for(int i=1;i+len-1<=n;i++)//关系一般为2<=i<=k<j<=n
{
int j=i+len-1;//j的求值，开始点+区间长度-1
for(int k=i;k<j;k++)
{
f[i][j]=min/max(状态转移方程,f[i][j]);
// 一般为f[i][k] 运算符 f[k+1][j]...
// 可以理解为合并i到k和k+1到j这两个区间，同时进行操作
}
}
}
接下来看看例题吧
区间合并求值问题
石子合并
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=250;
int f[N][N],g[N][N];
int a[N],s[N];
int main()
{
int n;
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 i=1;i<=n;i++)
{
f[i][i]=0;
}
for(int len=2;len<=n;len++)
{
for(int i=1;i+len-1<=n;i++)
{
int j=i+len-1;
for(int k=i;k<j;k++)
{
f[i][j]=min(f[i][k]+f[k+1][j]+s[j]-s[i-1],f[i][j]);
g[i][j]=max(g[i][k]+g[k+1][j]+s[j]-s[i-1],g[i][j]);
}
}
}
cout<<f[1][n]<<endl;
cout<<g[1][n];
}
环状区间DP
区间DP还有一类特殊题型，把原本的线性结构拓展到环状结构。
这比较好处理，只需要把数据复制，再贴到原来的数据后面。
能量项链
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=1000;
int n;
int a[N],f[N][N];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
a[i+n]=a[i];//拓展操作
}
for(int len=2;len<=n;len++)
{
for(int i=1;i<=n*2+1-len;i++)
{
int j=i+len-1;
for(int k=i;k<j;k++)
{
if(f[i][j]<f[i][k]+f[k+1][j]+a[i]*a[1+k]*a[j+1])
{
f[i][j]=f[i][k]+f[k+1][j]+a[i]*a[1+k]*a[j+1];
}
}
}
}
int ans=0;
for(int i=1;i<=n*2;i++)
{
ans=max(f[i][i+n-1],ans);
}
cout<<ans;
}
多边形
这道题的难点在于它同时有负数和乘号，我们无法正常的求最大值，因为负数乘负数为一个正数。
因此我们要同时维护一个最大值和一个最小值。思路就是这样，看代码吧。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=1000;
int n;
struct lmy
{
int num;
char ch;
}a[N];
int f[N][N],g[N][N],s[N];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i].ch>>a[i].num;
a[i+n].ch=a[i].ch;
a[i+n].num=a[i].num;
}
memset(f,-0x3f,sizeof(f));
memset(g,0x3f,sizeof(g));
for(int i=1;i<=2*n;i++)
{
f[i][i]=g[i][i]=a[i].num;
}
for(int len=1;len<=n;len++)
{
for(int i=1;i<=2*n-len+1;i++)
{
int j=i+len-1;
for(int k=i;k<j;k++)
{
if(a[k+1].ch=='t')
{
f[i][j]=max(f[i][k]+f[k+1][j],f[i][j]);
g[i][j]=min(g[i][k]+g[k+1][j],g[i][j]);
}
if(a[k+1].ch=='x')
{
int h1=f[i][k]*f[k+1][j];
int s1=g[i][k]*g[k+1][j];
int w1=max(h1,s1);
int h2=f[i][k]*g[k+1][j];
int s2=g[i][k]*f[k+1][j];
int w2=min(h2,s2);
f[i][j]=max(w1,f[i][j]);
int w3=min(g[i][j],g[i][k]*g[k+1][j]);
g[i][j]=min(w2,w3);
}
}
}
}
int ans=0;
for(int i=1;i<=n*2;i++)
{
ans=max(ans,f[i][i+n-1]);
}
cout<<ans<<endl;
for(int i=1;i<=n;i++)
{
if(f[i][i+n-1]==ans)
{
cout<<i<<" ";
}
}
}
总结
区间DP可能比较难理解，但它的应用比较简单，只要记住模板，找到状态转移方程，就可以解决问题。
好了，就到这里了，拜拜。