【蓝桥每日一题]-动态规划 （保姆级教程 篇11）#方格取数2.0 #传纸条

今天继续讲方格中取数类，不过是跑两次的问题

目录

题目：方格取数

  思路： 

题目：传纸条

  思路： 

---

   

题目：方格取数

  （跑两次）

     

思路： 

如果记录一种方案后再去跑另一个方案，影响因素太多了，所以两个方案要同时开跑。

那怎么让两种方案同时开跑呢？

               

既然dfs(x,y)是一种方案，那么dfs(x1,y1,x2,y2)不就代表两种方案了吗。

只不过dfs(x,y)有两种转移路径，dfs(x1,y1,x2,y2)有四种。分别为下下，下右，右右，右下

        

     

即：设置 f[x][y][x2][y2]当第一种方案走到x,y ，第二种方案走到x2,y2时取得的最大数。

要注意不要重复取数，也即是两种方案同时走到了同一个格子，这种情况要去重。

    

然后就是递归方程：

if (xmax(M,dfs(x+1,y,x2+1,y2)+s[x+1][y]+s[x2+1][y2]-s[x+1][y]*(x+1==x2+1&&y==y2));//都向下走，如果有重复，减去重复
if (xmax(M,dfs(x+1,y,x2,y2+1)+s[x+1][y]+s[x2][y2+1]-s[x+1][y]*(x+1==x2&&y==y2+1));//方案1向下，2向右
if (ymax(M,dfs(x,y+1,x2+1,y2)+s[x][y+1]+s[x2+1][y2]-s[x][y+1]*(x==x2+1&&y+1==y2));//方案1向右，2向下
if (ymax(M,dfs(x,y+1,x2,y2+1)+s[x][y+1]+s[x2][y2+1]-s[x][y+1]*(x==x2&&y+1==y2+1));//都向右走

然后调用dfs(1,1,1,1)即可

#include 
using namespace std; 
int N=0;
int s[15][15],f[11][11][11][11];
int dfs(int x,int y,int x2,int y2)
{
    if (f[x][y][x2][y2]!=-1) return f[x][y][x2][y2];//记忆化
    if (x==N&&y==N&&x2==N&&y2==N) return 0;//如果两种方案都走到了终点，返回0，不要返回终点格子值 
    int M=0;
    if (xmax(M,dfs(x+1,y,x2+1,y2)+s[x+1][y]+s[x2+1][y2]-s[x+1][y]*(x+1==x2+1&&y==y2));//都向下走，如果有重复，减去重复
    if (xmax(M,dfs(x+1,y,x2,y2+1)+s[x+1][y]+s[x2][y2+1]-s[x+1][y]*(x+1==x2&&y==y2+1));//方案1向下，2向右
    if (ymax(M,dfs(x,y+1,x2+1,y2)+s[x][y+1]+s[x2+1][y2]-s[x][y+1]*(x==x2+1&&y+1==y2));//方案1向右，2向下
    if (ymax(M,dfs(x,y+1,x2,y2+1)+s[x][y+1]+s[x2][y2+1]-s[x][y+1]*(x==x2&&y+1==y2+1));//都向右走
    f[x][y][x2][y2]=M;//记录这种情况 
    return M;//返回最大值 
}
int main()
{
    int x,y,t;cin>>N;
    for(int a=0;a<=N;a++)//不能memset了，必须初始化成-1，否则dfs会死循环
      for(int b=0;b<=N;b++)
        for(int c=0;c<=N;c++)
          for(int d=0;d<=N;d++) f[a][b][c][d]=-1;
	while(cin>>x>>y>>t&&(x+y+t))s[x][y]=t;
    cout<<dfs(1,1,1,1)+s[1][1];//输出，因为dfs中没有考虑第一格，即s[1][1]，所以最后要加一下 
    return 0;
}

    

    

题目：传纸条

     

    

思路： 

     

一样的思路，要同时开始跑才行。

    

f[x1][y1][x2][y2]表示走到两个方案分别走到(x1,y1)(x2,y2)的最优解，因为两个方案走的哈曼顿距离是一样的，可以优化成f[k][x1][x2]表示走到(x1,k-x1)(x2,k-x2)的最优解。

      

为什么这么做呢！

一是充分性：因为两种方案是捆绑在一起跑的，所以哈曼顿距离一定是一样的。

二是必要性：这样的话遍历的时候不会出现错误的状态，也就是两个方案会走到各种各样的点，可能有的两点到原点的哈曼顿距离就不一样，这是不允许的

        
转移方程：f(k,x1,x2)=max{f(k-1,x1,x2)，f(k-1,x1,x2-1)，f(k-1,x1-1,x2)，f(k-1,x1-1,x2-1)}，分别为来自左左，左上，上左，上上，然后减去重复即可。

      
注意：1，两个人不能走同一个格子，所以x1!=x2   （这里就已经保证了不交叉）  
           2，1<=k-x1<=m;故 x1<=k-1且x1>=k-m  同理x2<=k-1且x2>=k-m
   

        

#include
using namespace std;
const int N = 55;
int n, m;
int g[N][N];
int f[N*2][N][N];
int main()
{
    scanf("%d%d", &n, &m);
    for (int i=1; i<=n; i++)
    for (int j=1; j<=m; j++){
        scanf("%d", &g[i][j]);
	}
    for (int k=2; k<=n+m; k++)
    for (int x1=max(1,k-m); x1<=min(k-1,n); x1++)
    for (int x2=max(1,k-m); x2<=min(k-1,n); x2++){
    	int t=g[x1][k-x1];//当前好心度
    	if(x2!=x1) t+=g[x2][k-x2];
    	for (int a=0; a<=1; a++)
    	for (int b=0; b<=1; b++){
    		f[k][x1][x2]=max(f[k][x1][x2],f[k-1][x1-a][x2-b]+t);
		}
	}
    printf("%d\n", f[n+m][n][n]);
    return 0;
}