分析

• 分析题意：我们要从起点到终点走两次取最大值，且每个点最多只能走一次

• 摘花生是起点到终点走一次取最大值

• 让两条路同时走：

• $[i_1,j_1],[i_2,j_2]$分别表示两条路此时的位置

• 我们可以注意到$i_1+j_1==i_2+j_2$(两条路在同一时刻走过的距离一定是相等的)

• 那么我们设计一个状态$f[k][i_1][i_2]$其中k表示的是此时$i_1+j_1$的和(即当前两条路走过的距离)

• 下面分析状态转移(以当前点[i,j]作为划分),它能由以下四个状态转移过来

• 第一条路径向下，第二条路径向下 $f[k][i_1][i_2]<-f[k-1][i_1-1][i_2-1]$

• 第一条路径向下，第二条路径向右$f[k][i_1][i_2]<-f[k-1][i_1-1][i_2]$

• 第一条路径向右，第二条路径向下$f[k][i_1][i_2]<-f[k-1][i_1][i_2-1]$

• 第一条路径向右，第二条路径向右$f[k][i_1][i_2]<-f[k-1][i_1][i_2]$

• 再通过$i_1==i_2$来判断是否走到了同一个点，如果走到同一个点则只加1次，否则加2次

时间复杂度(状态数量(N^3),状态转移(O(1))->O(N^3)

代码

import java.io.*;


public class Main{

    public static void main(String[] args) throws IOException{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.valueOf(in.readLine());
        int[][] g = new int[n+1][n+1];
        while(true){
            String[] s = in.readLine().split("\\s+");
            int a = Integer.valueOf(s[0]);
            int b = Integer.valueOf(s[1]);
            int c = Integer.valueOf(s[2]);
            if(a == 0 && b == 0 && c == 0) break;
            g[a][b] = c;
        }
        int[][][] f = new int[2*n+1][n+1][n+1];
        for(int k = 2 ; k <=2*n;k++){
            for(int i1 = 1 ; i1 <= n ; i1++){
                for(int i2 = 1 ; i2 <= n ; i2++){
                    int j1 = k-i1,j2 = k-i2;
                    if(j1 > 0 && j1 <= n && j2 > 0 && j2 <= n){
                        int t = g[i1][j1];
                        if(i1 != i2) t+=g[i2][j2];
                        // 1->下,2->下
                        f[k][i1][i2] = Math.max(f[k][i1][i2],f[k-1][i1-1][i2-1]+t);
                        // 1->下,2->右
                        f[k][i1][i2] = Math.max(f[k][i1][i2],f[k-1][i1-1][i2]+t);
                        // 1->右,2->下
                        f[k][i1][i2] = Math.max(f[k][i1][i2],f[k-1][i1][i2-1]+t);
                        // 1->右,2->右
                        f[k][i1][i2] = Math.max(f[k][i1][i2],f[k-1][i1][i2]+t);
                    }
                }
            }
        }
        System.out.println(f[2*n][n][n]);
    }
}