Problem 2234 牧场物语
Accept: 95 Submit: 434
Time Limit: 1000 mSec Memory Limit : 32768 KB
Problem Description
小茗同学正在玩牧场物语。该游戏的地图可看成一个边长为n的正方形。
小茗同学突然心血来潮要去砍树，然而，斧头在小茗的右下方。
小茗是个讲究效率的人，所以他会以最短路程走到右下角，然后再返回到左上角。并且在路上都会捡到/踩到一些物品，比如说花朵，钱和大便等。
物品只能被取最多一次。位于某个格子时，如果格子上还有物品，就一定要取走。起点和终点上也可能有物品。
每种物品我们将为其定义一个价值，当然往返之后我们取得的物品的价值和越大越好。但是小茗同学正在认真地玩游戏，请你计算出最大的价值和。
Input
多组数据(<=10)，处理到EOF。
第一行输入正整数N(N≤100)，表示正方形的大小。
接下来共N行，每行N个整数Ai,j(|Ai,j|≤10^9)，表示相应对应位置上物品的价值。值为0表示没有物品。
Output
每组数据输出一个整数，表示最大价值和。
Sample Input
2
11 14
16 12
11 14
16 12
Sample Output
53
Source
福州大学第十三届程序设计竞赛
题目链接： http://acm.fzu.edu.cn/problem.php?pid=2234
题目分析：有点像kaka矩阵那个问题，但是这题可能有负圈，不好用费用流做，考虑用动态规划，从左上到右下再返回，我们可以等价为两人同时从左上到右下的过程，dp[i][j][k]表示第一个人横坐标在i，第二个人横坐标在j，当前两人各走了k步时的最大值，因为走了k步又知道横坐标，纵坐标是可以求出来的，然后枚举四种情况即 A下B下，A下B右，A右B下，A右B右，转移一下即可，当两人走到同一点时权值只加一遍
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;
ll const INF = 1e18;
int const MAX = 105;
ll a[MAX][MAX], dp[MAX][MAX][MAX << 1];
int n;int main()
{while(scanf("%d", &n) != EOF){for(int k = 0; k <= 2 * n - 2; k++)for(int i = 0; i <= n; i++)for(int j = 0; j <= n; j++)dp[i][j][k] = -INF;for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++)scanf("%I64d", &a[i][j]);dp[1][1][0] = a[1][1];for(int k = 1; k <= 2 * n - 2; k++){for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++){int x1 = i;int y1 = k - i + 2;int x2 = j;int y2 = k - j + 2;if(x1 == 1 && x2 == 1 && y1 == 1 && y2 == 1)continue;if(y1 >= 1 && y1 <= n && y2 >= 1 && y2 <= n){ll val = 0;if(x1 == x2 && y1 == y2)val += a[x1][y1];else val += a[x1][y1] + a[x2][y2];dp[x1][x2][k] = max(dp[x1][x2][k], dp[x1 - 1][x2][k - 1] + val);dp[x1][x2][k] = max(dp[x1][x2][k], dp[x1][x2 - 1][k - 1] + val);dp[x1][x2][k] = max(dp[x1][x2][k], dp[x1 - 1][x2 - 1][k - 1] + val);dp[x1][x2][k] = max(dp[x1][x2][k], dp[x1][x2][k - 1] + val);}}}}printf("%I64d\n", dp[n][n][2 * n - 2]);}
}
