numtri.cpp

USACO Section 1-4的后两个程序以及Section 1-5的全部程序代码

/*
NAME:lemon_c1
LANG:C++
PROG:numtri
*/
#include<cstdio>
int a[1001][1001];
int f[1001][1001];
int n;
inline int max(int t1,int t2)
{
	return (t1>t2)?t1:t2;
}
int main(void)
{
	FILE *fin=fopen("numtri.in","r");
	FILE *fout=fopen("numtri.out","w");
	fscanf(fin,"%d",&n);
	for(int i=0;i<n;i++)
		for(int j=0;j<=i;j++)
			fscanf(fin,"%d",&a[i][j]);
	for(int i=0;i<n;i++)
		f[n-1][i]=a[n-1][i];
	for(int i=n-2;i>=0;i--)
		for(int j=0;j<=i;j++)
			f[i][j]=max(f[i+1][j],f[i+1][j+1])+a[i][j];
	fprintf(fout,"%d\n",f[0][0]);
	fclose(fin);
	fclose(fout);
	return 0;
}