学步园

http://acm.hdu.edu.cn/showproblem.php?pid=2686

 多进程DP，昨天第一次听说...

题目大意是找两条从(1, 1) 到(n, n)的路径，使权值和最大且节点不重叠。

让两个进程同时进行，枚举步数K，当x1==x2||y1==y2时跳过，得状态转移方程：

dp(k, x1, y1, x2, y2) = max(dp(k-1, x1-1, y1, x2-1, y2), dp(k-1, x1-1, y1, x2, y2-1), dp(k-1, x1, y1-1, x2-1, y2), dp(k-1, x1, y1-1,x2, y2-1)) 

+ data(x1, y1) + data(x2, y2) ; 

由于只能走右或下，所以坐标满足x+y=k。这样就能降低维数为3维，方程：

dp(k, x1, x2) = max(dp(k-1, x1, x2), dp(k-1, x1-1, x2), dp(k-1, x1, x2-1), dp(k-1, x1-1, x2-1)) + data(x1, k-x1) + data(x2, k-x2) ;

code:

#include<cstdio>
#include<cstring>
#define Max(a, b)   a>b?a:b
int data[31][31], dp[62][31][31] ;
int max(int a, int b, int c, int d){
    a = Max(a, b) ;
    c = Max(c, d) ;
    a = Max(a, c) ;
    return a ;
}
int main(){
    int n, i, j, k ;
    while(~scanf("%d", &n)){
        for(i=0; i<n; i++)
            for(j=0; j<n; j++)
                scanf("%d", &data[i][j]) ;
        memset(dp, 0, sizeof(dp)) ;
        for(k=1; k<2*n-2; k++){
            for(i=0; i<=k; i++){
                for(j=0; j<=k; j++){
                    if(i==j||i>=n||j>=n)    continue ;
                    dp[k][i][j] = max(dp[k-1][i][j], dp[k-1][i-1][j], dp[k-1][i][j-1], dp[k-1][i-1][j-1]) ;
                    dp[k][i][j] += data[i][k-i] + data[j][k-j] ;
                }
            }
        }
        dp[k][n-1][n-1] = Max(dp[k-1][n-2][n-1], dp[k-1][n-1][n-2]) + data[n-1][n-1] + data[0][0] ;
        printf("%d\n", dp[k][n-1][n-1]) ;
    }
    return 0 ;}