1073.cpp

自己在nankai上面做的一部分题

#include <cstdio>
#include <memory>
int score[1001][1001],f[1001][1001],n;

int max(int x,int y)
{return x>y?x:y;}
void calc()
{
	int i,j;
	memset(f,0,sizeof(f));
	for (i=0;i<=n;i++)
	{
		f[i][i+1]=f[i][0]=0;
	}
	for (i=1;i<=n;i++)
	{
		for (j=1;j<=i;j++)
		{
			f[i][j]=max(f[i-1][j-1],f[i-1][j])+score[i][j];
		}
	}
}

int main()
{
	int i,j,temp;
	while (scanf("%d",&n)==1)
	{
		temp=0;
		for (i=1;i<=n;i++)
		{
			for (j=1;j<=i;j++)
			{
				scanf("%d",&score[i][j]);
			}
		}
		calc();
		for (i=1;i<=n;i++)
		{if (temp<f[n][i]) temp=f[n][i];}
		printf("%d\n",temp);
	}
	return 1;
}