PKU Judge Online 1163 The Triangle

■1163 The Triangle

□Problem
ピラミッド状になっている数字がある．

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

このピラミッドを一番上(ここでは7)から左下/右下へたどって行き，総和を取る．この総和の最大値を出力せよ．この例では，30(7->3->8->7->5)が最大値．

□Solution
下からDPしていくだけ．

□Code

view plainprint?

1. package p1163;  
2.   
3. import java.util.*;  
4. import java.lang.*;  
5. import java.math.*;  
6. import java.io.*;  
7.   
8. import static java.lang.Math.*;  
9. import static java.util.Arrays.*;  
10.   
11. public class Main{  
12.   
13.     Scanner sc=new Scanner(System.in);  
14.   
15.     final int INF=Integer.MAX_VALUE;  
16.     final double EPS=1e-9;  
17.   
18.     void run(){  
19.         int n=sc.nextInt();  
20.         int[][] a=new int[n][n];  
21.         for(int j=0; j<n; j++)  
22.             for(int i=0; i<j+1; i++)  
23.                 a[j][i]=sc.nextInt();  
24.   
25.         for(int j=n-2; j>=0; j--)  
26.             for(int i=0; i<j+1; i++)  
27.                 a[j][i]+=max(a[j+1][i], a[j+1][i+1]);  
28.         println(a[0][0]+"");  
29.     }  
30.   
31.     void print(String s){  
32.         System.out.print(s);  
33.     }  
34.   
35.     void println(String s){  
36.         System.out.println(s);  
37.     }  
38.   
39.     public static void main(String[] args){  
40.         // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
41.         new Main().run();  
42.     }  
43. }  

package p1163;

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

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

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+1; i++)
                a[j][i]=sc.nextInt();

        for(int j=n-2; j>=0; j--)
            for(int i=0; i<j+1; i++)
                a[j][i]+=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();
    }
}