PKU Judge Online 3176 Cow Bowling

■3176 Cow Bowling

□Problem

          7
        3   8
      8   1   0
    2   7   4   4
  4   5   2   6   5

このようなピラミッドを上から底辺までたどっていく．たどって来た数字を全て足し合わせたた合計の最大値を求めよ．

□Solution
下からDPしていく．

□Code

package p3176;

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

// AC
public class Main{

    Scanner sc=new Scanner(System.in);

    final int INF=Integer.MAX_VALUE;
    final double EPS=1e-9;

    void run(){
        int n=sc.nextInt();
        int[][] a=new int[n][n];
        for(int j=0; j<n; j++)
            for(int i=0; i<=j; i++)
                a[j][i]=sc.nextInt();
        for(int j=n-2; j>=0; j--)
            for(int i=0; i<=j; i++)
                a[j][i]+=Math.max(a[j+1][i], a[j+1][i+1]);
        println(""+a[0][0]);
    }

    void print(String s){
        System.out.print(s);
    }

    void println(String s){
        System.out.println(s);
    }

    public static void main(String[] args){
        // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
        new Main().run();
    }
}