VIJOS1493 - [NOIP2008]传纸条

2016/11/17

见识到了双线程DP。

因为题目的意思就是找两条不相交的最长路,所以说有四个维度(相当于DP里面又跑了一个DP):

一条 (1, 1) 到 (x1, y1) 的最大路径与另一条 (1, 1) 到 (x1, y1) 的不相交最大路径的总长

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <cstdio>
#include <cstring>
#include <limits>
using namespace std;
const int MAX_N = 50 + 10;
int M, N;
int W[MAX_N][MAX_N];
int F[MAX_N][MAX_N][MAX_N][MAX_N];

void DP() {
    for(int i1=1;i1<=M;i1++) {
        for(int j1=1;j1<=N;j1++) {
            for(int i2=1;i2<=M;i2++) {
                for(int j2=1;j2<=N;j2++) {
                    int maxV = max(max(F[i1-1][j1][i2-1][j2], F[i1-1][j1][i2][j2-1]),
                                   max(F[i1][j1-1][i2-1][j2], F[i1][j1-1][i2][j2-1]));
                    if(i1 == i2 && j1 == j2)
                        F[i1][j1][i2][j2] = W[i1][j1] + maxV;
                    else
                        F[i1][j1][i2][j2] = W[i1][j1] + W[i2][j2] + maxV;
                }
            }
        }
    }
}

int main() {
    cin >> M >> N;
    for(int i=1;i<=M;i++) {
        for(int j=1;j<=N;j++) {
            cin >> W[i][j];
        }
    }

    DP();
    cout << F[M][N][M][N] << endl;
}