区间DP(石子合并及同类题)-一一网

【摘要】石子合并1 题意：一条直线上摆放着一行共n堆的石子。现要将石子有序地合并成一堆。规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆石子数记为该次合并的得分。请编辑计算出将n堆石子合并成一堆的最小得分和将n堆石子合并成一堆的最大得分。
还是比较好理解的，我们先求出n堆石子的前缀和，这样我们求新合成的一堆石子数只需要知道这堆石子的前后位置作差即可，再考虑怎么合成，我们首…

石子合并1
题意：一条直线上摆放着一行共n堆的石子。现要将石子有序地合并成一堆。规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆石子数记为该次合并的得分。请编辑计算出将n堆石子合并成一堆的最小得分和将n堆石子合并成一堆的最大得分。

还是比较好理解的，我们先求出n堆石子的前缀和，这样我们求新合成的一堆石子数只需要知道这堆石子的前后位置作差即可，再考虑怎么合成，我们首先构造二维数组DP[i][j]表示从第i位置到第j位置为新合成的一堆石子的得分，DP[i][j]的合成方式有多种，可以是DP[i][i]+DP[i+1][j]，DP[i][i+1]+DP[i+2][j]，……DP[i][j-1]+DP[j][j]这些情况用一个通式dn[i][k]+dn[k+1][j]+sum[j]-sum[i-1]｛i<=k<j}表示，前半部分表示不同的合成方式，后面的sum[j]-sum[i-1]是从第i位置到第j位置新合成的这一堆石子的个数(得分)，k的范围一定要弄清楚，可以等于i表示由第i个与第i+1到j这一大个合成的；不等于j，当k=j-1时，表示由第i到j-1这一大个与第j个合成的，这为最后一种合成情况。
再在每种情况里取最小值与最大值即可。

注意：由于DP[i][j]的值的确定是多种方式中取的最优，所以我们需要将每一次的结果都与DP[i][j]比较，需要对其赋初始值以保证第一次的结果正确，求最小得分我们对其赋大值，最大得分赋0即可，注意赋的大值不是随便赋一个数，过大的数会使其数据溢出，不算太大的数会使其结果错误，总结发现，对一个整形变量我们对其赋值0x3f3f3f3f较好，数组初始化memset(dp,0x3f,sizeof(dp))较好，数据不溢出且答案正确
详细解释

#include<iostream>
#include<cstring>
using namespace std;
int a[205],sum[205]= {0},dn[205][205],dx[205][205];
int main()
{   int n,i,j,k; int minn=0x3f3f3f3f,maxx=-1; while(cin>>n) {   minn=0x3f3f3f3f,maxx=-1; memset(dx,0,sizeof(dx)); memset(dn,0x3f,sizeof(dn)); for(i=1; i<=n; i++) {   cin>>a[i]; sum[i]=sum[i-1]+a[i];//计算前缀和 dn[i][i]=0;//一个石子，没有合成时，初始条件是0 } for(int len=2; len<=n; len++)//长度从2开始，表示由两个石子合并成一个 { for(i=1; i+len-1<=n; i++)//i+len-1为区间的右端点j { j=i+len-1; for(k=i; k<j; k++) { dn[i][j]=min(dn[i][j],dn[i][k]+dn[k+1][j]+sum[j]-sum[i-1]); dx[i][j]=max(dx[i][j],dx[i][k]+dx[k+1][j]+sum[j]-sum[i-1]); } } } cout<<dn[1][n]<<" "<<dx[1][n]<<endl; } return 0;
}

  
 
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33

石子合并2
题意：在圆形操场上摆放着一行共n堆的石子。现要将石子有序地合并成一堆。规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆石子数记为该次合并的得分。请编辑计算出将n堆石子合并成一堆的最小得分和将n堆石子合并成一堆的最大得分。

这个题和上一个题的区别是圆形范围，情况变多了，因为是一个环，最后一个可以和第一个和并。在这里插入图片描述
也就是考虑的范围应该是1 2 3 4 5 6 1 2 3 4 5 6，即2*n，处理方式与上面相同，但最后需要比较从不同位置开始的长度为n（说明n个石子合并成了一个，只是合成的起始位置不同）的石子个数的结果

#include<iostream>
#include<cstring>
using namespace std;
int a[205],sum[205],dn[205][205],dx[205][205];
int main()
{ int n,i,j,k,minn=0x3f3f3f3f,maxx=-1; while(cin>>n) {   minn=0x3f3f3f3f,maxx=-1; memset(dx,0,sizeof(dx)); memset(dn,0x3f,sizeof(dn)); for(i=1; i<=n; i++) {   cin>>a[i]; sum[i]=sum[i-1]+a[i]; dn[i][i]=0; } for(i=n+1; i<=2*n; i++) {   sum[i]=sum[i-1]+a[i-n]; dn[i][i]=0; } for(int len=2; len<=n; len++) { for(i=1; i+len-1<=2*n; i++) { j=i+len-1; for(k=i; k<j; k++) { dn[i][j]=min(dn[i][j],dn[i][k]+dn[k+1][j]+sum[j]-sum[i-1]); dx[i][j]=max(dx[i][j],dx[i][k]+dx[k+1][j]+sum[j]-sum[i-1]); } } } for(i=1; i<=n; i++) { minn=min(minn,dn[i][i+n-1]);//比较不同位置开始的情况 maxx=max(maxx,dx[i][i+n-1]); } cout<<minn<<" "<<maxx<<endl; } return 0;
}

  
 
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36
  37
  38
  39
  40
  41
  42

P
题意：给你一串珠子，如果前一颗能量珠的头标记为m，尾标记为r，后一颗能量珠的头标记为r，尾标记为n，则聚合后释放的能量为mrn，新产生的珠子的头标记为m，尾标记为n。问只剩下一颗珠子使这串珠子释放的总能量最大。

这个问题类似于石子合并问题2，动态转移方程中前半部分珠串合成方式和石子合并一样为dp[i][k]+dp[k+1][j]，后面总能量单独求。由于每次合成一个新的珠子时，它的头标记和尾标记的值变化，发现头标记m的值就是前一部分dp[i][k]中首位置对应的值即a[i]，尾标记n的值为后一部分dp[k+1][j]的尾位置的下一位，即a[j+1]，画个图理解，以2 3 5 10为例
在这里插入图片描述
黑色的表示数字的位置，由图可知，r的值为a[k+1]
所以动态转移方程为dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]+a[i]*a[k+1]*a[j+1])

#include<iostream>
#include<cstring>
using namespace std;
int a[205],d[205][205];
int n,i,j,k;
int main()
{ while(cin>>n) {   int maxx=-1; memset(d,0,sizeof(d)); for(i=1; i<=n; i++) {   cin>>a[i]; a[i+n]=a[i]; } for(int len=2;len<=n;len++) { for(i=1,j=len; j<=2*n; i++,j++) { for(k=i; k<j; k++) { d[i][j]=max(d[i][j],d[i][k]+d[k+1][j]+a[i]*a[k+1]*a[j+1]); } } } for(i=1; i<=n; i++) { maxx=max(maxx,d[i][i+n-1]); } cout<<maxx<<endl; } return 0;
}

  
 
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32

C
题意：给你一行牌，每一张牌包括了一个正整数。在每一个移动中，玩家拿出一张牌，得分是用它的数字乘以它左边和右边的数，不允许拿第1张和最后1张牌。最后一次移动后，只剩下两张牌。你的目标是使得分的和最小。

这个题和上面合成珠子的题和石子合并1都很像，处理方式仿造石子合并1，dp[i][j]表示i到j区间里的得分和，倒着看这个题，我们把取数看成添数，即在i，j之间加k，然后下一个数字加到ik中间或者kj中间，依次类推，这里的i和j就相当于第一张牌和最后一张牌，不取，k和其他数是要取的牌。所以可以构建动态转移方程dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]+a[i]*a[k]*a[j](i<=k<j)，怎么对数组初始化呢，举个例子理解，如果i=1,j=2时，1和2为边界，不取，当k等于i时，dp[i][i]让它无穷大，同时dp[i][j]也要无穷大。因为我们最终要的是最小值，我们一开始可以对数组初始化让它无穷大，以上i=1，j=2的那种情况满足，如果i=1,j=3，1和3为边界不取，考虑k=2的情况，因为a[1]*a[2]*a[3]即为结果，所以要对dp[1][2]和dp[2][3]赋0，其他区间同样，所以需要对dp[i][i+1]赋0。

#include<iostream>
#include<cstring>
using namespace std;
int a[205],d[205][205];
int n,i,j,k;
int main()
{ while(cin>>n) {   int minn=0x3f3f3f3f; memset(d,0x3f,sizeof(d)); for(i=1; i<=n; i++) {   cin>>a[i]; d[i][i+1]=0; } for(int len=2;len<=n;len++) { for(i=1,j=len; j<=n; i++,j++) { for(k=i; k<j; k++) { d[i][j]=min(d[i][j],d[i][k]+d[k][j]+a[i]*a[k]*a[j]); } } } cout<<d[1][n]<<endl; } return 0;
}

  
 
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28