题目描述

blablabla

样例

blablabla

算法1

(DP) $O(n^3)$

blablabla

时间复杂度

参考文献

Java 代码

import java.util.*;
import java.io.*;

public class Main{
    private static int N, n, m;
    private static int[][][] f;
    private static int[][] w;
    private static Scanner jin = new Scanner(System.in);
    static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    public static void main(String[] args) throws Exception{
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        w = new int[n+1][m+1];
        f = new int[n+m+2][n+1][n+1];
        // build graph
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                w[i][j] = in.nextInt();
            }
        }
        in.close();

        for (int k = 2; k <= n+m ; k++){ 
            int l = Math.max(1, k-m);   //  1 <= x1 <= n, 1 <= k-x1 <= m
            int r = Math.min(n, k-1);
            for(int i1 = l; i1 <= r; i1++){
                for(int i2 = l; i2 <= r; i2++){
                    for (int a = 0; a <= 1; a ++ ){
                        for (int b = 0; b <= 1; b ++ ){
                            if (i1 != i2 || k == 2 || k == n + m)
                            {
                                int t = w[i1][k - i1] + w[i2][k-i2];
                                f[k][i1][i2] = Math.max(f[k][i1][i2], f[k - 1][i1 - a][i2 - b] + t);
                            }
                        }
                    }
                }
            }
        }

       System.out.println(f[n+m][n][n]);
    }
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla