FZU 2234

tiberius 2018-03-02 原文

题目为中文，题意略。

这个题目我开始用贪心做bfs两次，这样做是错的，因为两次局部的最优解并不能得出全局的最优解，以下面样例说明：

0 10 -1

10 10 10

1 0 10

第一次贪心后：

0 10 -1

0 0 0

1 0 0

第二次贪心后：

0 0 -1

0 0 0

1 0 0

这样贪心取到的值是50，然而我们完全有方案取到51。

为什么会造成这样的状况呢？是因为我们没有枚举出所有状态，而且说明了全局的最优不等于局部最优之和。

我们首先要确认，从左上到右下，再返回左上，和两个人同时从左上出发，最终同时到达右下是等效的。

我们定义dp[i][j][k]—-第一个人横坐标是i，第二个人横坐标是j，当前已走k步，所能获取最大值。由于小茗走的是最短路，

所以我们可以利用k求得横坐标相应的纵坐标

详见代码：

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#define maxn 105
using namespace std;
typedef long long LL;
const LL INF = 1e14;

LL dp[maxn][maxn][2];
LL value[maxn][maxn];
int n;
int mov1[] = {0,0,-1,-1};
int mov2[] = {0,-1,0,-1};

int main(){
    while(scanf("%d",&n) == 1){
        for(int k = 0;k < 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",&value[i][j]);
            }
        }
        dp[1][1][0] = value[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){
                    dp[i][j][k & 1] = -INF;
                    int x1 = i,x2 = j;
                    int y1 = 1 + (k - (i - 1)),y2 = 1 + (k - (j - 1));
                    if(y1 < 1 || y1 > n || y2 < 1 || y2 > n) continue;
                    //printf("now is (%d,%d) (%d,%d)....\n",x1,y1,x2,y2);
                    for(int c = 0;c < 4;++c){
                        int xx1 = x1 + mov1[c],xx2 = x2 + mov2[c];
                        int yy1 = 1 + ((k - 1) - (xx1 - 1)),yy2 = 1 + ((k - 1) - (xx2 - 1));
                        if(xx1 < 1 || xx2 < 1 || yy1 < 1 || yy2 < 1) continue;
                        if(dp[xx1][xx2][(k - 1) & 1] == -INF) continue;
                        LL add = 0;
                        if(x1 == x2 && y1 == y2) add = value[x1][y1];
                        else add = value[x1][y1] + value[x2][y2];
                        //printf("from (%d,%d) (%d,%d)\n",xx1,yy1,xx2,yy2);
                        dp[x1][x2][k & 1] = max(dp[x1][x2][k & 1],dp[xx1][xx2][(k - 1) & 1] + add);
                    }
                    //printf("maxvalue: %I64d\n",dp[x1][x2][k]);
                }
            }
        }
        LL ans = dp[n][n][(2 * n - 2) & 1];
        printf("%I64d\n",ans);
    }
    return 0;
}

/*
3
0 10 -1
10 10 10
1 0 10
*/