题目描述

设有 N \times NN×N 的方格图 (N \le 9)(N≤9)，
我们将其中的某些方格中填入正整数，而其他的方格中则放入数字 00。
某人从图的左上角的 AA 点出发，可以向下行走，也可以向右走，直到到达右下角的 BB 点。在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字 00）。
此人从 AA 点到 BB 点共走两次，试找出 22 条这样的路径，使得取得的数之和为最大。

思路

$f[i][j][x][y]$是第一条路径和加上第二条路经和的最大和。

( i , j ) 是第一条的坐标;
( x , y ) 是第二条的坐标;

则状态转移方程为:
当两条路径重合时，即i = x , j = y时 {
$f[i][j][x][y] = max ( f[i][j][x][y] , f[i - 1][j][x - 1][y] ) ;$ ( 都向下走 )
$f[i][j][x][y] = max ( f[i][j][x][y] , f[i - 1][j][x][y - 1] ) ;$ ( 一上一右 )
$f[i][j][x][y] = max ( f[i][j][x][y] , f[i][j - 1][x - 1][y] ) ;$ ( 一右一上 )
$f[i][j][x][y] = max ( f[i][j][x][y] , f[i][j - 1][x][y - 1] ) ;$ ( 都向右走 )
$f[i][j][x][y] += g[i][j] ;$ ( 取数 )
}
else {
$f[i][j][x][y] = max ( f[i][j][x][y] , f[i - 1][j][x - 1][y] ) ;$ ( 都向下走 )
$f[i][j][x][y] = max ( f[i][j][x][y] , f[i - 1][j][x][y - 1] ) ;$ ( 一上一右 )
$f[i][j][x][y] = max ( f[i][j][x][y] , f[i][j - 1][x - 1][y] ) ;$ ( 一右一上 )
$f[i][j][x][y] = max ( f[i][j][x][y] , f[i][j - 1][x][y - 1] ) ;$ ( 都向右走 )
$f[i][j][x][y] += g[i][j] + g[x][y] ;$ ( 取数 )
}

代码

#include <bits/stdc++.h>

using namespace std ;

const int N = 1e1 + 5 ;

int n ;
int g[N][N] ;
int f[N][N][N][N] ;

int main ( ) {

    cin >> n ;
    while ( 1 ) {

        int a , b , c ;
        cin >> a >> b >> c ;

        if ( a == 0 ) break ;
        g[a][b] = c ;

    }

    for ( int i = 1 ; i <= n ; i ++ )
        for ( int j = 1 ; j <= n ; j ++ ) 
            for ( int x = 1 ; x <= n ; x ++ ) 
                for ( int y = 1 ; y <= n ; y ++ )
                    if ( i == x && j == y ) {

                        f[i][j][x][y] = max ( f[i][j][x][y] , f[i - 1][j][x - 1][y] ) ;
                        f[i][j][x][y] = max ( f[i][j][x][y] , f[i - 1][j][x][y - 1] ) ;
                        f[i][j][x][y] = max ( f[i][j][x][y] , f[i][j - 1][x - 1][y] ) ;
                        f[i][j][x][y] = max ( f[i][j][x][y] , f[i][j - 1][x][y - 1] ) ;

                        f[i][j][x][y] += g[i][j] ; 

                    }
                    else {

                        f[i][j][x][y] = max ( f[i][j][x][y] , f[i - 1][j][x - 1][y] ) ;
                        f[i][j][x][y] = max ( f[i][j][x][y] , f[i - 1][j][x][y - 1] ) ;
                        f[i][j][x][y] = max ( f[i][j][x][y] , f[i][j - 1][x - 1][y] ) ;
                        f[i][j][x][y] = max ( f[i][j][x][y] , f[i][j - 1][x][y - 1] ) ;

                        f[i][j][x][y] += g[i][j] + g[x][y] ;

                    }

    cout << f[n][n][n][n] ;

    return 0 ;

}