小灶第五次作业 dp

小灶第五次作业 dp"/>

小灶第五次作业 dp

题目大意：

　　一个n*m的格子，Baker Vai要从（1,1）到（n,m）再回到（1,1），每到一个格子可以收集格子上的数字（每个格子只能走一次，（1,1）这个格子除外），问最终搜集的数字之和最大为多少？

解题思路：

　　可以把题目转化为求两个对象同时从（1,1）出发到（n,m）途中不能相遇，状态转移的时候可以用dp[step][x][y]，step代表当前步数，x，y分别代表两者当前所在的行（所在列可以直接求出来）。显然step = m+n-1 时候是走到了右下角，题目要求只能向下走或者向左走，于是就说明你不可能绕圈圈，换句话说你只能离目标越来越近，不可能是绕道远的地方再回去，也就省了很多麻烦，横纵坐标之后和步数是有明确的关系的，同时，无论你之前怎么选某一个位置都可以得到，不用担心错过和比较大的。然后就是状态方程：ans = max(两个都向下，一个向右一个向下，一个向下一个向右，都向右）注意，记忆化搜索，如果以前搜到这里过，直接返回，每一层算最后的ans加上的是本层的两个人数，如果两个横坐标相同，那么第二个就不要了。

#include <iostream>
#include <cstdio>
#include <cstring>using namespace std;int a[110][110],dp[220][110][110];
int n, m;int  dfs(int step,int r1,int r2)
{if(step == n+m-1){if(r1 == r2 && r1 == n && step-r1+1 == m)return a[r1][step-r1+1 ];elsereturn -1;}int ans = dp[step][r1][r2];if(ans != -1)return ans;if(r1 < n && r2 < n)ans = dfs(step+1,r1+1,r2+1);if(r1 < n && step-r2+1 < m)ans = max(ans,dfs(step+1,r1+1,r2));if(r2 < n && step-r1+1 < m)ans = max(ans,dfs(step+1,r1,r2+1));if(step-r1+1 < m&&step-r2+1 < m)ans = max(ans,dfs(step+1,r1,r2));ans +=  a[r1][step-r1+1] + ((r1==r2)?0:a[r2][step-r2+1]);dp[step][r1][r2] = ans;return ans;
}int main()
{int T;scanf("%d",&T);for (int i = 1 ; i <= T ; i++){scanf("%d%d",&n,&m);for (int j = 1 ; j <= n ; j++)for (int k = 1 ; k <= m ; k++)scanf("%d",&a[j][k]);memset(dp,-1,sizeof(dp));printf("Case %d: %d\n",i,dfs(1,1,1));}return 0;
}