hdu2686_多线程dp

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2686

题意：从(1, 1)到(n, n)再到(1, 1).

右下到左上只能左， 上；左上到右下只能右，下。

思路：设两个人同时从(1, 1)出发，如果同时到(i, j)，跳过

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

int dp[35][35][35], num[35][35], n;
int main()
{
    while(~scanf("%d", &n))
    {
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                scanf("%d", &num[i][j]);
        memset(dp, 0, sizeof(dp));
        dp[1][1][1] = num[1][1];
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                for(int k = 1; k < i + j && k <= n; k++)
                {
                    if(i == n && j == n)
                        dp[i][j][k] = num[n][n] + max(dp[n - 1][n][n], dp[n][n - 1][n - 1]);
                    else if(i == k)
                        continue;
                    else
                    {
                        dp[i][j][k] = num[i][j] + num[k][i + j - k] + max(max(dp[i - 1][j][k - 1], dp[i][j - 1][k - 1]), max(dp[i - 1][j][k], dp[i][j - 1][k]));
                    }
                }
            }
        }
        printf("%d
", dp[n][n][n]);
    }
    return 0;
}