2010年9月12日日曜日

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
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();
}
}

0 件のコメント: