POJ - 3176 Cow Bowling解题报告（求三角形数最大路）

社团里以前做过。

#include<iostream>
#include<string.h>

using namespace std;
int n;
int dp[400][400]={0};
int a[400][400]={0};
int my_max(int x,int y)
{
	if(x>y)return x;
	return y;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=i;j++)
		{
			cin>>a[i][j];
		}
	}
	dp[1][1]=a[1][1];
	for(int i=2;i<=n;i++)
	{
		for(int j=1;j<=i;j++)
		{
			dp[i][j]=a[i][j]+my_max(dp[i-1][j-1],dp[i-1][j]);
		}
	}
	int max=0; 
	for(int i=1;i<=n;i++)
	{
		if(max<dp[n][i])max=dp[n][i];
	}
	cout<<max;
	memset(dp,0,sizeof(dp));
	memset(a,0,sizeof(a));
}