我找了个AC的程序，随机了n组数据，两个程序跑出的结果是一样的，但是始终是wa。。。o(╯□╰)o
这题有没有什么trick？
附wa的代码
#include <iostream>
#include <math.h>
using namespace std;
struct node
{
	int id;
	double x,y;
	double v;
	double l;
};
node mm[20];
int ans,ansnum,ansv;
double ansleft;
bool vis[20];
double cal(node x)
{
	return sqrt(x.x*x.x+x.y*x.y);
}
double cal2(node aa,node bb)
{
	return sqrt((aa.x-bb.x)*(aa.x-bb.x)+(aa.y-bb.y)*(aa.y-bb.y));
}
double tubao(int x,int n)
{
	int i;
	node temp;
	int sid;
	temp.id=-1;
	temp.x=999999999;
	temp.y=999999999;
	for(i=0;i<n;i++)
	{
		if(vis[i])continue;
		if(temp.x==mm[i].x&&temp.y>mm[i].y)
		{
			temp=mm[i];
		}
		if(temp.x>mm[i].x)
		{
			temp=mm[i];
		}
	}
	if(temp.id==-1)return 0;
	sid=temp.id;
	node last,nn;
	last.x=0;
	last.y=-1;
	int tt;
	double sum;
	sum=0;
	do
	{
		double cos,tempcos;
		cos=-2;
		for(i=0;i<n;i++)
		{
			if(i==temp.id)continue;
			if(vis[i])continue;
			nn.x=mm[i].x-temp.x;
			nn.y=mm[i].y-temp.y;
			tempcos=(last.x*nn.x+last.y*nn.y)/(cal(last)*cal(nn));
			if(tempcos>cos)
			{
				cos=tempcos;
				tt=i;
			}
		}
		if(tt<0||tt>=n)return 0;
		sum+=cal2(temp,mm[tt]);
		last.x=mm[tt].x-temp.x;
		last.y=mm[tt].y-temp.y;
		temp=mm[tt];
	}while(temp.id!=sid);
	return sum;
}
void work(int x,int n)
{
	int i;
	memset(vis,0,sizeof(vis));
	int num;
	double val;
	double sum;
	sum=0;
	val=0;
	num=0;
	for(i=0;i<n;i++)
	{
		if(x&(1<<i))
		{
			vis[i]=1;
			sum+=mm[i].l;
			num++;
			val+=mm[i].v;
		}
	}
	if(val==ansv&&ansnum<num)return ;
	if(val>ansv)return ;
	double len;
	len=tubao(x,n);
	if(len>sum)return ;
	if(val==ansv&&ansnum==num)
	{
		if(sum-len>ansleft)
		{
			ans=x;
			ansnum=num;
			ansleft=sum-len;
			ansv=val;
		}
	}
	else
	{
		ans=x;
		ansnum=num;
		ansleft=sum-len;
		ansv=val;
	}
}
void output(int x)
{
	int cnt;
	cnt=0;
	while(x)
	{
		cnt++;
		if(x%2)printf(" %d",cnt);
		x/=2;
	}
}
int main ()
{
//	freopen("in.txt","r",stdin);
//	freopen("out1.txt","w",stdout);
	int n,i;
	int cnt;
	cnt=0;
	while(scanf("%d",&n)!=EOF&&n)
	{
		cnt++;
		for(i=0;i<n;i++)
		{
			mm[i].id=i;
			scanf("%lf%lf%lf%lf",&mm[i].x,&mm[i].y,&mm[i].v,&mm[i].l);
		}
		ansnum=20;
		ansv=INT_MAX;
		for(i=1;i<(1<<n);i++)
		{
			work(i,n);
		}
		printf("Forest %d\n",cnt);
		printf("Cut these trees:");
		output(ans);
		printf("\nExtra wood: %.2lf\n\n",ansleft);
	}
	return 0;
}

• int tt;那一行改成int tt=-1; (2) lmm333 2011-07-25 23:07:00