北大ACM3176——Cow Bowling~数塔

北大ACM3176——Cow Bowling~~数塔

这一题，简单的动态规划。

状态转移方程：dp[i][j]  + = max(dp[i + 1][j], dp[i + 1][j + 1])；(i = n - 2 to 0; j = 0 to i)；

 最后输出dp【0】【0】就OK了。

下面是AC的代码：

#include <iostream>
#include <cstdio>
using namespace std;

int max(int x, int y)
{
	return x > y ? x : y;
}

int main()
{
	int n, i, j;
	int a[355][355];
	while(scanf("%d", &n) != EOF)
	{
		for(i = 0; i < n; i++)
			for(j = 0; j <= i; j++)
				scanf("%d", &a[i][j]);
		for(i = n - 2; i >= 0; i--)
		{
			for(j = 0; j <= i; j++)
			{
				a[i][j] += max(a[i + 1][j], a[i + 1][j + 1]);
			}
		}
		printf("%d\n", a[0][0]);
	}
	return 0;
}