【蓝桥杯】动态规划专题(DP)数据结构与算法qq41514794的博客-

1.传纸条

小渊和小轩是好朋友也是同班同学，他们在一起总有谈不完的话题。一次素质拓展活动中，班上同学安排做成一个 m 行 n 列的矩阵，而小渊和小轩被安排在矩阵对角线的两端，因此，他们就无法直接交谈了。幸运的是，他们可以通过传纸条来进行交流。纸条要经由许多同学传到对方手里，小渊坐在矩阵的左上角，坐标( 1,1 )，小轩坐在矩阵的右下角，坐标( m,n )。从小渊传到小轩的纸条只可以向下或者向右传递，从小轩传给小渊的纸条只可以向上或者向左传递。

在活动进行中，小渊希望给小轩传递一张纸条，同时希望小轩给他回复。班里每个同学都可以帮他们传递，但只会帮他们一次，也就是说如果此人在小渊递给小轩纸条的时候帮忙，那么在小轩递给小渊的时候就不会再帮忙。反之亦然。

还有一件事情需要注意，全班每个同学愿意帮忙的好感度有高有低（注意：小渊和小轩的好心程度没有定义，输入时用 00 表示），可以用一个 0-100 的自然数来表示，数越大表示越好心。小渊和小轩希望尽可能找好心程度高的同学来帮忙传纸条，即找到来回两条传递路径，使得这两条路径上同学的好心程度只和最大。现在，请你帮助小渊和小轩找到这样的两条路径。

输入格式

输入第一行有 2 个用空格隔开的整数 m 和 n ，表示班里有 m 行 n 列（ 1 le m,n le 501≤m,n≤50 ）。

接下来的 m 行是一个 m×n 的矩阵，矩阵中第 i行 j 列的整数表示坐在第 i 行 j 列的学生的好心程度。每行的 n 个整数之间用空格隔开。

输出格式

输出共一行，包含一个整数，表示来回两条路上参与传递纸条的学生的好心程度之和的最大值。

数据范围

30%30% 的数据满足：1 le m,n le 101≤m,n≤10

100%100% 的数据满足： 1 le m,n le 501≤m,n≤50

样例输入复制

 3 3 0 3 9 2 8 5 5 7 0

样例输出复制

 34

算法分析:本题要求一条从(1,1)到(m,n)，再从(m,n)到(1,1)的路径,我们可以看做是求(1,1)到(m,n)两条不同的最短路径,这两条路径只能向下或向右且不相交，计算出这两条路径的权值和的最大值即可。

两个人走，利用四维的数组 dp[i][j][k][l] 来保存路径中间过程的权值之和的最大值，其中 i j k l 分别表示两个人的位置,很容易想出状态转移方程:

为了方便表示,我们令 max  =max{dp[i-1][j][k-1][l], dp[i-1][j][k][l-1],dp[i][j-1][k-1][l],dp[i][j-1][k][l-1]};即为两个人向下走或者想右走得到的最大权值,则

dp[i][j][k][l]= max+map[i][j]+map[k][l]; 但是要注意如果有一个人走到了另一个人走到的位置(也就是i==k && j==l的时候),只能加一次权值也就是dp[i][j][k][l]= max+map[i][j];

 #include <bits/stdc++.h> using namespace std; int n,m,dp[55][55][55][55],a[55][55]; //dp[i][j][k][l]表示第一条路走到a[i][j],第二条路走到a[k][l]时好感度和的最大值。 //DP时分四种情况，还要注意判断两条路径是否相交。 int main() {     while (~scanf("%d%d",&n,&m))     {         memset(a,0,sizeof a);         memset(dp,0,sizeof dp);         for (int i=1;i<=n;++i){             for (int j=1;j<=m;++j){              scanf("%d",&a[i][j]);             }         }         for (int i = 1; i <=n; i++) {             for (int j = 1; j <=m; j++) {                 for (int k = 1; k <=n; k++) {                     int l=i+j-k;                     if(l<=0||l>m)                         continue;                     dp[i][j][k][l] = max(max(dp[i-1][j][k-1][l], dp[i-1][j][k][l-1]), max(dp[i][j-1][k-1][l],dp[i][j-1][k][l-1]));                     if(i==k && j==l)                          dp[i][j][k][l] += a[i][j];                      else                          dp[i][j][k][l]+=a[i][j]+a[k][l];                 }             }         }         printf("%dn",dp[n][m][n][m]);     }     return 0; }

2.乌龟棋

小明过生日的时候，爸爸送给他一副乌龟棋当作礼物。

乌龟棋的棋盘是一行 NN 个格子，每个格子上一个分数（非负整数）。棋盘第 11 格是唯一的起点，第 NN 格是终点，游戏要求玩家控制一个乌龟棋子从起点出发走到终点。

乌龟棋中 MM 张爬行卡片，分成 44 种不同的类型（MM 张卡片中不一定包含所有 44 种类型的卡片见样例），每种类型的卡片上分别标有 11、22、33、44 四个数字之一，表示使用这种卡片后，乌龟棋子将向前爬行相应的格子数。游戏中，玩家每次需要从所有的爬行卡片中选择一张之前没有使用过的爬行卡片，控制乌龟棋子前进相应的格子数，每张卡片只能使用一次。游戏中，乌龟棋子自动获得起点格子的分数，并且在后续的爬行中每到达一个格子，就得到该格子相应的分数。玩家最终游戏得分就是乌龟棋子从起点到终点过程中到过的所有格子的分数总和。

很明显，用不同的爬行卡片使用顺序会使得最终游戏的得分不同，小明想要找到一种卡片使用顺序使得最终游戏得分最多。

现在，告诉你棋盘上每个格子的分数和所有的爬行卡片，你能告诉小明，他最多能得到多少分吗？

输入格式

第 11 行 22 个正整数 NN 和 MM ，分别表示棋盘格子数和爬行卡片数。

第 22 行 NN 个非负整数，a_1a1​, a_2a2​, ……, a_NaN​，其中 a_iai​ 表示棋盘第 ii 个格子上的分数。

第 33 行 MM 个整数，b_1b1​ , b_2b2​, ……, b_MbM​ ，表示 MM 张爬行卡片上的数字。

输入数据保证到达终点时刚好用光 MM 张爬行卡片，即 N – 1 = sum_1^M{b_i}N−1=∑1M​bi​ 。

输出格式

输出只有 11 行，11 个整数，表示小明最多能得到的分数。

数据范围

对于 30%30% 的数据有 1 le N le 301≤N≤30， 1 le M le 121≤M≤12。

对于 50%50% 的数据有 1 le N le 1201≤N≤120 ，1 le M le 501≤M≤50，且 44 种爬行卡片，每种卡片的张数不会超过 2020。

对于 100%100% 的数据有 1 le N le 3501≤N≤350 ，1 le M le 1201≤M≤120 ，且 44 种爬行卡片，每种卡片的张数不会超过 4040；

0 le a_i le 1000≤ai​≤100，1 le i le N1≤i≤N ；1 le b_i le 41≤bi​≤4，1 le i le M1≤i≤M。输入数据保证 N – 1 = sum_1^M{b_i}N−1=∑1M​bi​ 。

样例输入1复制

 9 5 6 10 14 2 8 8 18 5 17 1 3 1 2 1

样例输出1复制

 73

样例输入2复制

 13 8 4 96 10 64 55 13 94 53 5 24 89 8 30 1 1 1 1 1 2 4 1

样例输出2复制

 455

 #include <cstdio> #include <iostream> #include <algorithm> #include <cstring> using namespace std; int f[42][42][42][42],i,n,m,num[5],a[400],k,l1,l2,l3,l4; int main() {     scanf("%d%d",&n,&m);  for (i=1;i<=n;i++){    scanf("%d",&a[i]);     }  memset(num,0,sizeof(num));  for (i=1;i<=m;i++){         scanf("%d",&k);    num[k]++;   }  memset(f,0,sizeof(0));  int t;  f[0][0][0][0]=a[1];  for (l1=0;l1<=num[1];l1++)    for (l2=0;l2<=num[2];l2++)      for(l3=0;l3<=num[3];l3++)        for(l4=0;l4<=num[4];l4++){                     t=l1+l2*2+l3*3+l4*4+1;         if(l1){                         f[l1][l2][l3][l4]=max(f[l1][l2][l3][l4],f[l1-1][l2][l3][l4]+a[t]);                     }         if(l2){                         f[l1][l2][l3][l4]=max(f[l1][l2][l3][l4],f[l1][l2-1][l3][l4]+a[t]);                     }                              if(l3){                         f[l1][l2][l3][l4]=max(f[l1][l2][l3][l4],f[l1][l2][l3-1][l4]+a[t]);                  }         if(l4){                         f[l1][l2][l3][l4]=max(f[l1][l2][l3][l4],f[l1][l2][l3][l4-1]+a[t]);                     }     }  printf("%d",f[num[1]][num[2]][num[3]][num[4]]); }

3.着色方案

有 nn 个木块排成一行，从左到右依次编号从 11 到 nn。你有 kk 种颜色的油漆，其中第 ii 种颜色的油漆足够涂 c_ici​ 个木块。

所有油漆刚好足够涂满所有木块，即 c_1+c_2+cdots +c_k = nc1​+c2​+⋯+ck​=n。相邻两个木块涂相同色显得很难看，所以你希望统计任意两个相邻木块颜色不同的着色方案。

输入格式

第一行为一个正整数 kk，第二行包含 kk 个整数 c_1+c_2+cdots +c_kc1​+c2​+⋯+ck​。

输出格式

输出一个整数，即方案总数模 10000000071000000007 的结果。

数据范围和提示

1 le k le 151≤k≤15， 1 le c_i le 51≤ci​≤5

样例输入复制

 3 1 2 3

样例输出复制

 10

 #include <cstring> #include <algorithm> #include <cstdio> #include <cstdlib> #include <cmath> using namespace std; typedef long long LL; const LL mod=1000000007; int k,tot[6]; LL dp[16][16][16][16][16][6]; LL DP(int a,int b,int c,int d,int e,int t){     if (dp[a][b][c][d][e][t] != -1)         return dp[a][b][c][d][e][t];     if (a + b + c + d + e == 0)         return dp[a][b][c][d][e][t]=1;     int A=a-(t==1),B=b-(t==2),C=c-(t==3),D=d-(t==4),E=e;     LL &res=dp[a][b][c][d][e][t];     res=0;     if (a)         res+=A*DP(a-1,b,c,d,e,0);     if (b)         res+=B*DP(a+1,b-1,c,d,e,1);     if (c)         res+=C*DP(a,b+1,c-1,d,e,2);     if (d)         res+=D*DP(a,b,c+1,d-1,e,3);     if (e)         res+=E*DP(a,b,c,d+1,e-1,4);     return res%=mod; } int main(){     memset(dp,-1,sizeof dp);     memset(tot,0,sizeof tot);     scanf("%d",&k);     for (int i=1,a;i<=k;i++){         scanf("%d",&a);         tot[a]++;     }     printf("%lld",DP(tot[1],tot[2],tot[3],tot[4],tot[5],0));     return 0; }