思路:两人一个从左上角出发只能向右和向下,另一人从右下角出发只能向左和向上,可以看做两人都是从右下角出发,且只能向左和向上传纸条,并且两条路径不会相交,因为一个人只会传一次,那么随便画一个图就能知道两条路径是闭合的图形。因此我们可以定义dp(x1, y1, x2, y2)是从(0, 0)出发第一人到达(x1, y1)处,第二人到达(x2, y2)处时能得到的最大好感度。两条路径的长度是一致的,即两人应该同时出发,因为dp(x1,
y1, x2, y2) = dp( x2, y2,x1, y1),所以约束(x2,
y2) 一定位于(x1, y1)的上方和右方,就能很好的开始转移了。
AC代码
#include <cstdio> #include <cmath> #include <cctype> #include <algorithm> #include <cstring> #include <utility> #include <string> #include <iostream> #include <map> #include <set> #include <vector> #include <queue> #include <stack> using namespace std; #pragma comment(linker, "/STACK:1024000000,1024000000") #define eps 1e-10 #define inf 0x3f3f3f3f #define PI pair<int, int> typedef long long LL; const int maxn = 50 + 5; int w[maxn][maxn], dp[maxn][maxn][maxn][maxn]; int n, m; const int dx[] = {0, -1}; const int dy[] = {-1, 0}; bool is_in(int x, int y) { if(x < 0 || x >= n || y < 0 || y >= m) return false; return true; } //两个人每次都要走一步 int dfs(int a, int b, int c, int d) { if(dp[a][b][c][d] != -1) return dp[a][b][c][d]; if(a == 0 && b == 0 && c == 0 && d == 0) return dp[a][b][c][d] = 0; int &ans = dp[a][b][c][d]; ans = -inf; for(int i = 0; i < 2; ++i){ int x1 = a + dx[i], y1 = b + dy[i]; if(!is_in(x1, y1)) continue; for(int j = 0; j < 2; ++j) { int x2 = c + dx[j], y2 = d + dy[j]; if(!is_in(x2, y2)) continue; if(x2 < x1 || y2 > y1 || (x1 == 0 && y1 == 0)) { int res = dfs(x1, y1, x2, y2); ans = max(ans, res + w[a][b] + w[c][d]); } } } return ans; } int main() { int T; scanf("%d", &T); while(T--) { scanf("%d%d", &n, &m); for(int i = 0; i < n; ++i) for(int j = 0; j < m; ++j) scanf("%d", &w[i][j]); memset(dp, -1, sizeof(dp)); printf("%d\n", dfs(n-1, m-1, n-1, m-1)); } return 0; }
如有不当之处欢迎指出!