shizihebing.cpp

算法中石子合并算法的实现

#include"stdio.h"

void hebing(int *p,int n,int t,int (*m)[100],int flag)
{
	int sum=0,s;
	for(int r=2;r<=n;r++)
	{
		for(int i=t;i<=n-r+t;i++)
		{
			int j=i+r-1;
			if(m[i%n][j%n]!=-1)
			{
				continue;
			}
			else if(m[i%n][j%n]==-1)
			{
				for(s=i;s<=j;s++)
					sum=sum+p[s%n];
				
				m[i%n][j%n]=m[(i+1)%n][j%n]+sum;
				sum=0;
				for(int k=i+1;k<j;k++)
				{
					for(s=i;s<=j;s++)
						sum=sum+p[s%n];
					int h=m[i%n][k%n]+m[(k+1)%n][j%n]+sum;
					sum=0;
					if(flag==1)
					{
						if(h<m[i%n][j%n])
							m[i%n][j%n]=h;
					}
					if(flag==0)
					{
						if(h>m[i%n][j%n])
						m[i%n][j%n]=h;
					}
				}
			}
		}
	}
}

main()
{
	int m[100][100],g[100][100],p[100],n,i,j,min,max;
	scanf("%d",&n);
	for(i=0;i<n;i++)
	{
		scanf("%d",&p[i]);
	}
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
		{
			if(i==j)
			{	
				m[i][j]=0;
				g[i][j]=0;
			}
			else
			{
				m[i][j]=-1;
				g[i][j]=-1;
			}
		}
	}
	
	for(i=n;i>0;i--)
	{
		hebing(p,n,i%n,m,1);
		hebing(p,n,i%n,g,0);
	}
	min=m[0][n-1];
	max=g[0][n-1];
	for(i=1;i<n;i++)
	{
		if(m[i][(i+n-1)%n]<min)
			min=m[i][(i+n-1)%n];
		if(g[i][(i+n-1)%n]>max)
			max=g[i][(i+n-1)%n];
	}
	printf("%d\n%d\n",min,max);
}