FZU 2234

题目为中文，题意略。

这个题目我开始用贪心做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][];

LL value[maxn][maxn];

int n;

int mov1[] = {,,-,-};

int mov2[] = {,-,,-};

int main(){

    while(scanf("%d",&n) == ){

        for(int k = ;k < ;++k){

            for(int i = ;i <= n;++i){

                for(int j = ;j <= n;++j){

                    dp[i][j][k] = -INF;

                }

            }

        }

        for(int i = ;i <= n;++i){

            for(int j = ;j <= n;++j){

                scanf("%I64d",&value[i][j]);

            }

        }

        dp[][][] = value[][];

        for(int k = ;k <=  * n - ;++k){

            for(int i = ;i <= n;++i){

                for(int j = ;j <= n;++j){

                    dp[i][j][k & ] = -INF;

                    int x1 = i,x2 = j;

                    int y1 =  + (k - (i - )),y2 =  + (k - (j - ));

                    if(y1 <  || y1 > n || y2 <  || y2 > n) continue;

                    //printf("now is (%d,%d) (%d,%d)....\n",x1,y1,x2,y2);

                    for(int c = ;c < ;++c){

                        int xx1 = x1 + mov1[c],xx2 = x2 + mov2[c];

                        int yy1 =  + ((k - ) - (xx1 - )),yy2 =  + ((k - ) - (xx2 - ));

                        if(xx1 <  || xx2 <  || yy1 <  || yy2 < ) continue;

                        if(dp[xx1][xx2][(k - ) & ] == -INF) continue;

                        LL add = ;

                        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 & ] = max(dp[x1][x2][k & ],dp[xx1][xx2][(k - ) & ] + add);

                    }

                    //printf("maxvalue: %I64d\n",dp[x1][x2][k]);

                }

            }

        }

        LL ans = dp[n][n][( * n - ) & ];

        printf("%I64d\n",ans);

    }

    return ;

}

/*

3

0 10 -1

10 10 10

1 0 10
*/

ps：感谢fp大佬提供的数据

巴特西

FZU 2234

最新文章

热门文章