单纯的贪心肯定是有问题的，例如N=4,个数分别为：5,3,4,5。
                                             ——LouTianCheng

> #include <stdio.h>
> void main(void)
> {
> 	int n,m;
> 	unsigned int a[50005],b[50005],*p,*q,*r;
> 	int i,k;
> 	unsigned c,min,tm;
> 	while(1)
> 	{
> 		scanf("%d",&n);
> 		if(n==0)
> 			break;
> 		for(i=1;i<=n;i++)
> 			scanf("%d",&a[i]);
> 		m = 0;a[0]=b[0]=1000000005;
> 		p = a+1; q = b+1; c = 2;
> 		while(n>1)
> 		{
> 			min = p[n] = 1000000005;
> 			k = 0;
> 			for(i=0;i<n;i++)
> 			{
> 				tm = p[i]+p[i+1];
> 				if(tm<=c)
> 				{
> 					m += tm;
> 					q[k] = tm;
> 					i++;
> 				}
> 				else
> 					q[k] = p[i];
> 				if(q[k]+q[k-1]<min)
> 					min = q[k-1]+q[k];
> 				k++;
> 			}
> 			c = min;
> 			r = p;			p = q;			q = r;
> 			n = k;
> 		}
> 		printf("%u\n",m);
> 	}
> }

• Re:谢谢，但5，3，4，5应该是多少呢 (104) PC0400322032 2004-08-09 21:59:32
  • 34 (50) bobpkuhj 2004-08-10 14:11:21