动态规划：区间DP与环形DP

区间型动态规划的典型例题是石子归并，同时使用记忆化搜索实现区间动归是一种比较容易实现的方式，避免了循环数组实现的时候一些边界的判断

n堆石子排列成一条线，我们可以将相邻的两堆石子进行合并，合并之后需要消耗的代价为这两堆石子的质量之和，问最小的合并代价

状态转移方程很容易给出：

f[i][j]=min(f[i][j],f[i][k]+f[k+][j]+sum[i][j])

因为要计算区间和，考虑前缀和进行预处理

然后我们给出用记忆化搜索形式实现的代码，这里的记忆化搜索形式可以作为后续问题的一个模板

 #include<iostream>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int INF=0x3f3f3f3f;

 const int maxn=;

 int n;

 int w[maxn];

 int g[maxn];  //前缀和

 int f[maxn][maxn];

 int dfs(int l,int r)

 {

     if(l==r) return ;

     if(f[l][r]!=INF)

         return f[l][r];

     int tmp=INF;

     for(int i=l;i<r;i++)

         tmp=min(tmp,dfs(l,i)+dfs(i+,r)+g[r]-g[l-]);

     if(tmp<f[l][r])

     f[l][r]=tmp;

     return f[l][r];

 }

 int main()

 {

     cin>>n;

     for(int i=;i<=n;i++)

     {

         cin>>w[i];

         g[i]=g[i-]+w[i];

     }

     for(int i=;i<=n;i++)

     for(int j=;j<=n;j++)

         f[i][j]=0x3f3f3f3f;

     cout<<dfs(,n)<<endl;

     return ;

 }

这个问题还是比较显然的，我们考虑另一个问题，那就是环形动态规划

其实环形动态规划也是区间型，只不过区间首尾相接

此时使用记忆化搜索实现，其实是不容易的

典型例题是能量项链

先给出状态转移方程：

f[i][j]=max(f[i][j],f[i][k]+f[k][j]+a[i]*a[j]*a[k])

由于每一种区间问题的价值计算方式不一样，可能采用不同的优化形式，本题直接计算即可

然后我们给出使用循环数组方式实现的一个固定的格式，所有的区间型动态规划都可以采取这样的形式来实现

 #include<iostream>

 #include<cstring>

 using namespace std;

 const int maxn=;

 int n;

 int a[maxn];

 long long ans=;

 int f[maxn][maxn];

 void dp()

 {

     for(int l=;l<=n;l++)  //区间长度

     for(int i=;i<=n*-l+;i++)  //区间起点

     {

         int j=i+l;  //区间终点

         for(int k=i+;k<=j-;k++)  //区间中任意点

             f[i][j]=max(f[i][j],f[i][k]+f[k][j]+a[i]*a[j]*a[k]);

     }

     for(int i=;i<=n;i++)

     if(ans<f[i][i+n])

         ans=f[i][i+n];

 }

 int main()

 {

     cin>>n;

     for(int i=;i<=n;i++)

     {

         cin>>a[i];

         a[n+i]=a[i];

     }

     dp();

     cout<<ans;

     return ;

 }

分别枚举区间的长度，区间的起点和区间中的任意点就好了

巴特西

动态规划：区间DP与环形DP

最新文章

热门文章