stones6ok.c

Problem F:汽车加油 Time Limit:1000MS Memory Limit:65536K Total Submit:1400 Accepted:404 Language

#include<stdio.h>
int stones[200];
int fangzhen[200][200];
int count1,count2;
int tempt1,tempt2;
int all;
int min;
int max;

int addup(int begin,int end)
{
	int count1,together=0;
	for(count1=begin;count1<=end;count1++)
	{
		together=together+stones[count1];
	}
	return together;
}

main()
{
	int i,j;
	scanf("%d",&all);
	for(count1=0;count1<all;count1++)
	{
		scanf("%d",stones+count1);
		stones[count1+all]=stones[count1];
	}

	for(i=0;i<all;i++)
	{
		for(j=0;j<all*2;j++)
		{
			if(i+j==2*all)break;
			else

			if(i==0)fangzhen[j][j+i]=0;
			else 
			if(i==1)fangzhen[j][j+i]=stones[j]+stones[j+i];
			else
			{
				tempt2=fangzhen[j][j]+fangzhen[j+1][i+j]+addup(j,j+i);
				for(count1=0;count1<i;count1++)
				{
					tempt1=fangzhen[j][j+count1]+fangzhen[j+count1+1][j+i]+addup(j,j+i);
					if (tempt2>tempt1)
						tempt2=tempt1;
				}
				fangzhen[j][j+i]=tempt2;
			}
			
		}
	}

	tempt2=fangzhen[0][all-1];
	for(count1=0;count1<all;count1++)
	{
		tempt1=fangzhen[count1][count1+all-1];
		if(tempt2>tempt1)
			tempt2=tempt1;
	}
	min=tempt2;
/*下面求最大*/
	for(i=0;i<all;i++)
	{
		for(j=0;j<all*2;j++)
		{
			if(i+j==2*all)break;
			else
			if(i==0)fangzhen[j][j+i]=0;
			else 
			if(i==1)fangzhen[j][j+i]=stones[j]+stones[j+i];
			else
			{
				tempt2=fangzhen[j][j]+fangzhen[j+1][i+j]+addup(j,j+i);
				for(count1=0;count1<i;count1++)
				{
					tempt1=fangzhen[j][j+count1]+fangzhen[j+count1+1][j+i]+addup(j,j+i);
					if (tempt2<tempt1)
						tempt2=tempt1;
				}
				fangzhen[j][j+i]=tempt2;
			}
			
		}
	}

	tempt2=fangzhen[0][all-1];
	for(count1=0;count1<all;count1++)
	{
		tempt1=fangzhen[count1][count1+all-1];
		if(tempt2<tempt1)
			tempt2=tempt1;
	}
	max=tempt2;
	printf("%d\n%d",min,max);
	
}