WUPC 2012 D - 三角パズル

問題

atcoder.jp

問題概要

N段の直角三角形状の数列が与えられる。
例)
7
2 3
1 5 4
頂点からスタートして真下もしくは右下に行くことが出来る。底辺までたどり着いたときに経路中の数値の合計の最大値を求めよ。
上の例だと7+3+5=15

解法

上からi番目、左からj番目の数をa[i][j]とする。

dp[i][j] : a[i][j]まで到達したときの経路中の数値の最大値
0≦i≦N-1、0≦j≦i

a[i][j]には上(a[i-1][j])からもしくは左上(a[i-1][j-1])から来るのでそこまでの最大値を持っておけばそこからa[i][j]までの最大値が分かる。

dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+a[i][j]

i=0もしくはj=0ときは配列外参照になるので別な処理をする。
(i)i=0かつj=0のとき
dp[i][j]=a[i][j]
(ii)i≠0かつj=0のとき
dp[i][j]=dp[i-1][j]+a[i]

i=j(≠0)のときは左上からしか行けないので
dp[i][j]=dp[i-1][j-1]+a[i][j]
(dp[i-1][j]=0よりmax(dp[i-1][j],dp[i-1][j-1])=dp[i-1][j-1]なのでこの場合分けはなくても大丈夫)

ソースコード

signed main() {
	int N;
	cin >> N;
	vector<vector<int>>a(N, vector<int>(N));
	rep(i, N) {
		rep(j, i + 1) {
			cin >> a[i][j];
		}
	}
	vector<vector<int>>dp(N, vector<int>(N));
	rep(i, N) {
		rep(j, i + 1) {
			if (i == 0 && j == 0) {
				dp[i][j] = a[i][j];
			}
			else if (i != 0 && j == 0) {
				dp[i][j] = dp[i - 1][j] + a[i][j];
			}
			else if (i == j) {
				dp[i][j] = dp[i - 1][j - 1] + a[i][j];
			}
			else {
				dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + a[i][j];
			}
		}
	}
	int ans = 0;
	rep(i, N) {
		rep(j, i + 1) {
			if (i == N - 1) {
				ans = max(ans, dp[i][j]);
			}
		}
	}
	cout << ans << endl;
}