生活随笔
收集整理的这篇文章主要介绍了
区间动态规划
小编觉得挺不错的,现在分享给大家,帮大家做个参考.
1、矩阵连乘，tyvj 1198(最优矩阵连乘)，关键是写出动态转移方程。用DP[i][j]表示矩阵Ai乘到Aj的最优解，P[]用来存储矩阵的行和列，M[i-1]表示矩阵i的行，M[i]表示矩阵i的列。
当i==j时，DP[i][i]=0；
当i<j时，可以假设他从k位置隔开。比方说从A3..A8。那么A1A2(A3A4A5A6A7A8)A9。我们知道若A矩阵为r1*c的矩阵，A2为c*r2的矩阵，得到的将是一个r1*r2的矩阵，且连乘次数为r1*c*r2。假设我从5位置隔开，就可以分为A1A2((A3A4A5)(A6A7A8))A9。那么这个时候的次数为：DP[3][5]+DP[6][8]+M[2]*M[5]*M[8](A3的行*A5的列*A8的列)。那么我只需要模举这其中的组合然后取最小值即可，这个时候的动态转移方程为:DP[i][j]=min(DP[i][k]+DP[k+1][j]+M[i-1]*M[k]*M[j])(i<=k<j)。
问题是：你要知道DP[i][k]和DP[k+1][j]的值，你才可以和DP[i][j]做比较，才能求出DP[i][j]的值。
思想是先求出相邻组的连乘次数，如一开始算相邻两个相乘，如图：
那么每两个相乘的结果我们可以得到。同理继续求三个相邻的结果。
计算的话比方说要求A1A2A3，可以化为(A1)(A2A3)=DP[1][1]+DP[2][3]+M[0]*M[1]*M[3]，依次类推结果为:DP[i][j]=DP[i][i]+DP[i+1][j]+M[i-1]*M[i]*M[j]。
只有这样做后我才可以求任意组合的次数，求出三个一组的结果后，我就可以求任意的四个矩阵连乘的最小值。如:A4A5A6A7，随便怎么组合，通过上面是计算都可以求出相应的结果。
现在讨论下范围：用r保存要求的每每相邻的组数(2<=r<=n)(从2开始是这里前提条件是i<j)，i的范围为：(1<=i<=n-r+1,稍作推理就知道，当r=3时，即三个三个一组时i<=9-3+1=7)，j的值固定j=r+i-1，具体见代码：
[cpp] view plaincopyprint?
#include<iostream> #include<cstring> #include<cstdio> using namespace std; const int MAX=110; #define min(a,b) (a)<(b)?(a):(b) #define CLR(arr,val) memset(arr,val,sizeof(arr)) int n,M[MAX],DP[MAX][MAX]; void Matrix() { for(int r=2;r<=n;r++) for(int i=1;i<=n-r+1;i++) { int j=r+i-1; DP[i][j]=DP[i+1][j]+M[i-1]*M[i]*M[j]; for(int k=i;k<j;k++) DP[i][j]=min(DP[i][k]+DP[k+1][j]+M[i-1]*M[k]*M[j],DP[i][j]); } } int main() { scanf("%d",&n); for(int i=0;i<=n;i++) scanf("%d",&M[i]); CLR(DP,0); Matrix(); cout<<DP[1][n]<<endl; return 0; }
路径输出：
[cpp] view plaincopyprint?
#include<iostream> #include<cstring> #include<cstdio> using namespace std; const int MAX=110; #define CLR(arr,val) memset(arr,val,sizeof(arr)) int n,M[MAX],DP[MAX][MAX],s[MAX][MAX]; void Matrix() { for(int r=2;r<=n;r++) for(int i=1;i<=n-r+1;i++) { int j=r+i-1; DP[i][j]=DP[i+1][j]+M[i-1]*M[i]*M[j]; s[i][j]=i; for(int k=i;k<j;k++) { int temp=DP[i][k]+DP[k+1][j]+M[i-1]*M[k]*M[j]; if(temp<DP[i][j]) { s[i][j]=k; DP[i][j]=temp; } } } } void Find(int i,int j) { if(i==j) { cout<<'A'<<i; return ; } if(i<s[i][j]) cout<<"("; Find(i,s[i][j]); if(i<s[i][j]) cout<<")"; if(s[i][j]+1<j) cout<<"("; Find(s[i][j]+1,j); if(s[i][j]+1<j) cout<<")"; } int main() { scanf("%d",&n); for(int i=0;i<=n;i++) scanf("%d",&M[i]); CLR(DP,0); Matrix(); Find(1,n); cout<<endl<<DP[1][n]<<endl; return 0; }
2、NYOJ 15(括号匹配)，令DP[i][j]表示字符串s的第i个字符到第j个字符需要添加的最少括号数。
①、当i==j时，只有一个符号，需再添加一个字符，所以DP[i][i]=1；
②、当i<j时，若是s[i]与S[j]配对，那么DP[i][j]=DP[i+1][j-1];
若是不配对，那么从中任选一个字符作为分界点，i<=k<j，就有:DP[i][j]=min(DP[i][j],DP[i][k]+DP[k][j])。具体实现和上例一样:
[cpp] view plaincopyprint?
#include<iostream> #include<string> #include<cstring> using namespace std; const int MAX=1010; #define min(a,b) (a)<(b)?(a):(b) #define CLR(arr,val) memset(arr,val,sizeof(arr)) string s; int n,DP[MAX][MAX]; bool pipei(char c1,char c2) { if(c1=='('&&c2==')'||c1=='['&&c2==']') return true; return false; } int main() { cin>>n; cin.get(); while(n--) { cin>>s; CLR(DP,0); int len=s.length(); for(int i=1;i<=len;i++) DP[i][i]=1; for(int r=2;r<=len;r++) for(int i=1;i<=len-r+1;i++) { int j=r+i-1; DP[i][j]=MAX; if(pipei(s[i-1],s[j-1])) DP[i][j]=DP[i+1][j-1]; for(int k=i;k<j;k++) DP[i][j]=min(DP[i][k]+DP[k+1][j],DP[i][j]); } cout<<DP[1][len]<<endl; } return 0; }
3、石子合并:Tyvj 1055(石子合并)，和这个题目类似的是Tyvj 1062(合并傻子)。
[cpp] view plaincopyprint?
#include<iostream> #include<cstring> using namespace std; const int MAX=1010; #define CLR(arr,val) memset(arr,val,sizeof(arr)) int n,a[MAX],sum[MAX][MAX],DP[MAX][MAX]; int Sand() { for(int r=2;r<=n;r++) for(int i=1;i<=n-r+1;i++) { int j=i+r-1; DP[i][j]=DP[i+1][j]+sum[i][j]; for(int k=i;k<j;k++) DP[i][j]=min(DP[i][j],DP[i][k]+DP[k+1][j]+sum[i][j]); } return DP[1][n]; } int main() { cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; CLR(DP,0); CLR(sum,0); for(int i=1;i<=n;i++) for(int j=i;j<=n;j++) sum[i][j]=sum[i][j-1]+a[j]; cout<<Sand()<<endl; return 0; }
4、加分二叉树。Tyvj 1073(加分二叉树)。
[cpp] view plaincopyprint?
#include<iostream> #include<cstring> using namespace std; const int MAX=50; #define CLR(arr,val) memset(arr,val,sizeof(arr)) long n,a[MAX],DP[MAX][MAX],s[MAX][MAX]; int flag=1; long Max() { for(int r=2;r<=n;r++) for(int i=1;i<=n-r+1;i++) { int j=i+r-1; DP[i][j]=DP[i+1][j]+a[i]; s[i][j]=i; for(int k=i+1;k<j;k++) { int temp=DP[i][k-1]*DP[k+1][j]+a[k]; if(temp>DP[i][j]) { DP[i][j]=temp; s[i][j]=k; } } } return DP[1][n]; } void Search(int L,int R) { if(L>R) return ; if(flag) flag=0; else cout<<" "; cout<<s[L][R]; if(L==R) return ; Search(L,s[L][R]-1); Search(s[L][R]+1,R); } int main() { cin>>n; CLR(DP,0); for(int i=1;i<=n;i++) { cin>>a[i]; DP[i][i]=a[i]; } cout<<Max()<<endl; for(int i=1;i<=n;i++) s[i][i]=i; Search(1,n); cout<<endl; return 0; }
题5：牢房：
描述
SB王国中有一个奇怪的监狱，这个监狱里一共有P间牢房，这些牢房一字排开，从左到右按1到P进行编号，第i间后面紧挨着第（i+1）间（最后一间除外）。现在有P名罪犯被关押在这P间牢房里。某一天，上级下发了一个释放名单，要求每天释放名单上的一个人。这可把监狱中的看守们吓得不轻，因为看守们知道，现在牢房中的P个人，可以相互之间传话。如果某个人离开了，那么原来和这个人能够传上话的人都会很气愤，导致他们那天会一直大吼大叫，搞得看守们很是头疼，但是如果给这些要发火的人吃上肉，他们就会安静。现在看守们想知道，如何安排释放的顺序，才能使得他们花费的肉钱最少。1<=p<=1000,1<=Q<=100
输入
第一行两个数P和Q，Q表示要释放名单上的人数；
第二行Q个数，表示释放哪些人
输出
仅一行，表示最少给多少人次送肉.
样例输入
20 3
3 6 14
样例输出
35
提示:（样例说明）
先释放14号监狱中的罪犯，要给1到13号监狱和15到20号监狱中的19人送肉吃；再释放6号监狱中的罪犯，要给1到5号监狱和7到13号监狱中的12人送肉吃；最后释放3号监狱中的罪犯，要给1到2号监狱和4到5号监狱中的4人送肉吃。
分析：用DP[i][j]表示在[i,j]区间所有该被释放的人都被释放的最小支付代价。
若是释放k，那么代价为DP[i][k-1]+DP[k+1][j]+(j-i)，所以动态转移方程为：DP[i][j]=min(DP[i][k-1]+DP[k+1][j]+(j-i)).
[cpp] view plaincopyprint?
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; const int MAX=1010; const int Inf=100000000; int n,m,a[MAX],sum[MAX],DP[MAX][MAX]; int main() { for(int i=0;i<MAX;i++) { fill(DP[i],DP[i]+MAX,Inf); DP[i][i]=0; } scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) scanf("%d",&a[i]); sort(a+1,a+m+1); for(int i=1;i<=m;i++) sum[i]=a[i]-a[i-1]-1; sum[m+1]=n-a[m]; for(int i=1;i<=m+1;i++) sum[i]=sum[i]+sum[i-1]; for(int i=m+1;i>=1;i--) for(int j=i+1;j<=m+1;j++) 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]+j-i-1); printf("%d\n",DP[1][m+1]); return 0; }
总结
以上是生活随笔为你收集整理的区间动态规划的全部内容，希望文章能够帮你解决所遇到的问题。
如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。
