1137.cpp

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

#include <cstdio>
#include <memory>
int mi[101][101],ma[101][101],n,stone[101];
int max(int x,int y)
{return x>y?x:y;}
int min(int x,int y)
{return x>y?y:x;}

void calc()
{
	int i,j;
	for (i=2;i<=n-1;i++)
	{
		for (j=1;j<=n;j++)
		{
			mi[j][i]=2*min(mi[j][i-1]+stone[(j+i-2)%n+1],stone[j]+mi[j%n+1][i-1]);
			ma[j][i]=2*max(ma[j][i-1]+stone[(j+i-2)%n+1],stone[j]+ma[j%n+1][i-1]);
		}
	}
}

int main()
{
	int i,da,xiao;
	while (scanf("%d",&n)!=EOF)
	{
		xiao=100000000;da=0;
		memset(mi,0,sizeof(mi));
		memset(ma,0,sizeof(ma));
		memset(stone,0,sizeof(stone));
		for (i=1;i<=n;i++)
		{
			scanf("%d",&stone[i]);
			mi[i][1]=ma[i][1]=stone[i];
		}
		calc();
		for (i=1;i<=n;i++)
		{
			if (da<(stone[i]+ma[i%n+1][n-1])) da=stone[i]+ma[i%n+1][n-1];
			if (xiao>(stone[i]+mi[i%n+1][n-1])) xiao=stone[i]+mi[i%n+1][n-1];
		}
		printf("%d\n",xiao);
		printf("%d\n",da);
	}
	return 1;
}