szjzt.cpp

这是学校ACM程序设计大赛的题目,拿出来大家算是当练习

#include <stdio.h>
#include <stdlib.h>

void dp(int **a, int total)
{
	int **array;
	array=(int **)malloc((total+2)*(total+2)*sizeof(int *));
	for(int i1=1; i1<=total; i1++)
		array[i1]=(int *)malloc((total+2)*sizeof(int));
/*	for(int j1=0; j1<=total; j1++)
		for(int k1=0; k1<=total; k1++)
			array[j1][k1]=0;*/


//	for(int i=1; i<=total; i++)
//		a[i][0]=0;
	for(int j=0; j<=total; j++)
		array[total][j]=a[total][j];
	for(int s=total-1; s>=1; s--)
	{
		for(int t=1; t<=s; t++)
		{
			if(array[s+1][t]>array[s+1][t+1])
				array[s][t]=a[s][t]+array[s+1][t];
			else
				array[s][t]=a[s][t]+array[s+1][t+1];
		}
	}
	printf("%d\n",array[1][1]);
}
void main()
{
	FILE *fp;
	if((fp=fopen("szjzt.in","r"))==NULL)
	{
		printf("can't open file\n");
		exit(0);
	}
	int circle;
	fscanf(fp,"%d",&circle);
	for(int i=0; i<circle; i++)
	{
		int total;
		fscanf(fp,"%d",&total);
		int **array;
		array=(int **)malloc((total+2)*(total+2)*sizeof(int *));
		for(int j=1; j<=total; j++)
			array[j]=(int *)malloc((total+2)*sizeof(int));
		for(int k=1; k<=total; k++)
			for(int s=1; s<=k; s++)
				fscanf(fp,"%d",&array[k][s]);
/*		for(k=1; k<=total; k++)
		{
			for(int s=1; s<=k; s++)
				printf("%d ",array[k][s]);
			printf("\n");
		}
		printf("*************\n");*/
//		printf("%d\n",array[1][3]);
		dp(array,total);
	}
}