卢氏八建公司最新抖音,google搜索优化方法,重庆在线直播,wordpress主题:精选zruckmetro主题目录
题目#xff1a;方格取数 思路#xff1a;
题目#xff1a;传纸条 思路#xff1a; 题目#xff1a;方格取数 #xff08;跑两次#xff09; 思路#xff1a; 如果记录一种方案后再去跑另一个方案#xff0c;影响因素太多了#xff0c;所以两个方案要同时开…目录
题目方格取数 思路
题目传纸条 思路 题目方格取数 跑两次 思路 如果记录一种方案后再去跑另一个方案影响因素太多了所以两个方案要同时开跑。 我们设置 f[x][y][x2][y2]当第一种方案走到x,y 第二种方案走到x2,y2时取得的最大数。 要注意不要重复取数也即是两种方案同时走到了同一个格子这种情况要去重。 然后就是递归方程 if (xNx2N) Mmax(M,dfs(x1,y,x21,y2)s[x1][y]s[x21][y2]-s[x1][y]*(x1x21yy2));//都向下走如果有重复减去重复
if (xNy2N) Mmax(M,dfs(x1,y,x2,y21)s[x1][y]s[x2][y21]-s[x1][y]*(x1x2yy21));//方案1向下2向右
if (yNx2N) Mmax(M,dfs(x,y1,x21,y2)s[x][y1]s[x21][y2]-s[x][y1]*(xx21y1y2));//方案1向右2向下
if (yNy2N) Mmax(M,dfs(x,y1,x2,y21)s[x][y1]s[x2][y21]-s[x][y1]*(xx2y1y21));//都向右走
也就是dfs(x,y,x2,y2)可以向下下下右右下右右四种情况递归。
#includeiostream
using namespace std; //流水的动归铁打的递推
int N0;
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 (xNyNx2Ny2N) return 0;//如果两种方案都走到了终点返回结束 int M0;if (xNx2N) Mmax(M,dfs(x1,y,x21,y2)s[x1][y]s[x21][y2]-s[x1][y]*(x1x21yy2));//都向下走如果有重复减去重复if (xNy2N) Mmax(M,dfs(x1,y,x2,y21)s[x1][y]s[x2][y21]-s[x1][y]*(x1x2yy21));//方案1向下2向右if (yNx2N) Mmax(M,dfs(x,y1,x21,y2)s[x][y1]s[x21][y2]-s[x][y1]*(xx21y1y2));//方案1向右2向下if (yNy2N) Mmax(M,dfs(x,y1,x2,y21)s[x][y1]s[x2][y21]-s[x][y1]*(xx2y1y21));//都向右走f[x][y][x2][y2]M;//记录这种情况 return M;//返回最大值
}
int main()
{int x,y,t;cinN;for(int a0;aN;a)//不能memset了必须初始化成-1否则dfs会死循环for(int b0;bN;b)for(int c0;cN;c)for(int d0;dN;d) f[a][b][c][d]-1;while(cinxyt(xyt))s[x][y]t;coutdfs(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 21k-x1m;故 x1k-1且x1k-m 同理x2k-1且x2k-m #includebits/stdc.h
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 i1; in; i)for (int j1; jm; j){scanf(%d, g[i][j]);}for (int k2; knm; k)for (int x1max(1,k-m); x1min(k-1,n); x1)for (int x2max(1,k-m); x2min(k-1,n); x2){int tg[x1][k-x1];//当前好心度if(x2!x1) tg[x2][k-x2];for (int a0; a1; a)for (int b0; b1; b){f[k][x1][x2]max(f[k][x1][x2],f[k-1][x1-a][x2-b]t);}}printf(%d\n, f[nm][n][n]);return 0;
}
