NOIP 2008 提高组 传纸条 解题报告

　　这题我以前就看过，一直不会做，后来看到别人说双线程动态规划，我以为是多么多么的神奇的一个东西，把它看的和Linux源码一样神奇了，现在学了之后也就是简单的DP，我用的四维DP，别人都说是三维，我先用四维做，以后再考虑三维（也许不会再考虑这一题了咯。）
　　我的方程如下:f[a][b][c][d] = max(f[a – 1][b][c – 1][d], f[a][b – 1][c – 1][d], f[a – 1][b][c][d – 1], f[a][b – 1][c][d – 1]) + map[a][b] + map[c][d].
　　a,b代表第一个线程（说线程夸张了一点），c,d代表第二个线程的坐标，map就是对应坐标的值。
　　代码如下：
#include <stdio.h>
#define max(a, b) ((a)>(b)?(a):(b))
int f[51][51][51][51];
int map[51][51];
int m, n;
int s[4];

volatile void test(int a, int b, int c, int d, int t)
{
        if(a < 0 || b < 0 || c < 0 || d < 0){
                return;
        }
        t = max(*t, f[a][b][c][d]);
}

void dp(void)
{
        int a = s[0], b = s[1], c = s[2], d = s[3];
        int t = 0;
        test(a – 1, b, c – 1, d, &t);
        test(a – 1, b, c, d – 1, &t);
        test(a, b – 1, c, d – 1, &t);
        test(a, b – 1, c – 1, d, &t);
        f[a][b][c][d] = t + map[a][b] + map[c][d];
}

void srch(int now)
{
        int i, k;
        if(now == 4){
                if(s[0] != s[2] || s[1] != s[3]){
                        dp();
                }
                return;
        }
        if(now & 1){
                k = n;
        }else{
                k = m;
        }
        for(i = 1; i <= k; i++){
                s[now] = i;
                srch(now + 1);
        }
}

int main(void)
{
        int i, j, k, l;
        scanf("%d%d", &m, &n);
        for(i = 1; i <= m; i++){
                for(j = 1; j <= n; j++){
                        scanf("%d", &map[i][j]);
                }
        }
        f[1][1][1][1] = map[1][1];
        srch(0);

        s[0] = s[2] = m;
        s[1] = s[3] = n;
        dp();

        printf("%d\n", f[m][n][m][n]);
        return 0;
}