动态规划(三):区间动态规划基础

Source
版权声明:转载请注明出处(作者转载的文章除外) https://blog.csdn.net/guoyangfan_/article/details/81162689

     继上文-背包动态规划

 (三):区间动态规划

    顾名思义,区间动态规划的题目一般来说是在操作每一个区间,(例如将两堆石子合并在一起,获得的价值是两堆石子的总价值)并获得相应的价值。当然,与线形动态规划有所不同的是,它要操作的子区间是要选择最优的。这时,我们就不能套用类似于线形动态规划的方程了,于是,便引出了区间动态规划。

   区间动态规划有属于自己的一类方程。

   f[i][j]=min(f[i][j],f[i][k]+f[k+1][j])   (k是目前阶段f[i][j]的选择的断点)

   i表示当前区间的左端点,j表示当前区间的右端点。

   那么,我们很容易看出这类方程的含义:将目前阶段f[i][j]分成两个子阶段f[i][k] 与 f[k+1][j],选择他们两个的和于目前的状态的最优解。

    简单的说一下,区间动态规划相当于将一个大的区间分成两个小的子区间,一般可以用循环或者搜索解决。

   直接说题目吧

   区间动态模板--luogu

  分析一下:

  在最初的第l~r石子合并之前,一定会有在这之前合并的两个区间。那么,这两个区间可以这么表示:f[l][k] 与 f[k+1][r];

  在我们处理链的时候,我们可以将n堆拓展为2n堆,其中第i堆与第i+n对完全相同。

  开始,我们用sum来维护前缀和;

  然后,我们将2n堆动态规划一下。

  那么,我们要求的答案就在f[1][n] 到 f[n][2n-1]之间。

#include<bits/stdc++.h>
using namespace std;
int n,sum[333],a[333],f1[500][500],f2[500][500];
int main()
{
	cin>>n;
	for(int i=1;i<=n;++i){
		cin>>a[i];
		a[i+n]=a[i];
	}
	sum[1]=a[1];
	for(int i=1;i<=n*2;++i){
		sum[i]=sum[i-1]+a[i];
		f1[i][i]=0;
		f2[i][i]=0;
	}
	for(int i=(n<<1)-1;i>0;--i)//这里,我们要从2n-1开始循环,因为我们已经将环断成链;
	{
		for(int j=i+1;j<i+n;++j)
		{
			f1[i][j]=40152137;//赋值一个大的数,这样便于之后的决策。
			for(int k=i;k<j;++k)
			{
				f1[i][j]=min(f1[i][j],f1[i][k]+f1[k+1][j]+sum[j]-sum[i-1]);
				f2[i][j]=max(f2[i][j],f2[i][k]+f2[k+1][j]+sum[j]-sum[i-1]);//动态规划方程,sum[j]-sum[i-1]表示当前最少要加上去的量。f2[i][k]+f2[k+1][j] 表示将f[i][j]分为两段,并用max取最优解,做出当前最优决策;
			}
		}
	}
	int minn=401521378,maxx=0;
	for(int i=1;i<=n;++i)
	{
		minn=min(f1[i][i+n-1],minn);
		maxx=max(f2[i][i+n-1],maxx);//选择最优解;
	}
	cout<<minn<<endl<<maxx;
	
}

 

 

   总结:

   区间动态规划类似于线形动态规划。那么我们就要深刻的理解的去理解动态规划的要领:要把多阶段过程转化为一系列单阶段问题,利用各阶段之间的关系,逐个求解。要锻炼出自己写出方程的能力。

  好,推荐几道题目:

  能量项链-luogu

  奶牛零食-luogu

  248-luogu