WUPC2012 D : 三角パズル

問題概要

パスカルの三角形を下っていくときの経路上の和の最大値を求める問題。

解法

DP。同じ問題がPOJなどいろんなところにある。

acceptされたコード

import std.stdio, std.conv, std.algorithm, std.string, std.array;

void main(){
	int n = to!int(readln.chomp);
	auto as = new int[][](n, 0);
	
	foreach(i; 0..n){
		as[i] = array(map!(to!int)(readln.chomp.split));
	}
	auto dp = new int[][](n, n);
	dp[0][0] = as[0][0];
	foreach(i; 0..n-1){
		foreach(j; 0..i+1){
			dp[i+1][j] = max(dp[i+1][j], dp[i][j] + as[i+1][j]);
			dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + as[i+1][j+1]);
		}
	}
	
	writeln( reduce!(max)(int.min, dp[$-1]) );
}