PKU 3176 Cow Bowling

• 動的計画法
• 左上と右上の値のうち大きい方を伝搬していく

int main() {
	int N;
	cin >> N;
	int dp[2][512];
	memset(dp, 0, sizeof(dp));

	int front = 1;
	int back = 0;
	int bestAnswer = INT_MIN;
	for (int row = 1; row <= N; ++row) {
		for (int column = 1; column <= row; ++column) {
			int value;
			cin >> value;
			dp[front][column] = value + max(dp[back][column - 1], dp[back][column]);
			bestAnswer = max(bestAnswer, dp[front][column]);
		}
		swap(front, back);
	}

	cout << bestAnswer << endl;
}