【poj】1873： The Fortified Forest （凸包+狀态壓縮+各種搞事）

題目描述：

The Fortified Forest

Time Limit: 1000MS	Memory Limit: 30000K
Total Submissions: 7818	Accepted: 2149

Description

Once upon a time, in a faraway land, there lived a king. This king owned a small collection of rare and valuable trees, which had been gathered by his ancestors on their travels. To protect his trees from thieves, the king ordered that a high fence be built around them. His wizard was put in charge of the operation. 

Alas, the wizard quickly noticed that the only suitable material available to build the fence was the wood from the trees themselves. In other words, it was necessary to cut down some trees in order to build a fence around the remaining trees. Of course, to prevent his head from being chopped off, the wizard wanted to minimize the value of the trees that had to be cut. The wizard went to his tower and stayed there until he had found the best possible solution to the problem. The fence was then built and everyone lived happily ever after. 

You are to write a program that solves the problem the wizard faced. 

樣例輸入：

6
 0  0  8  3
 1  4  3  2
 2  1  7  1
 4  1  2  3
 3  5  4  6
 2  3  9  8
3
 3  0 10  2
 5  5 20 25
 7 -3 30 32
0      

樣例輸出：

Forest 1
Cut these trees: 2 4 5 
Extra wood: 3.16

Forest 2
Cut these trees: 2 
Extra wood: 15.00
      

解題思路：

       因為n<=15，是以範圍不大。兩種方法：1.搜尋+凸包 2.狀态壓縮+凸包  事實上，因為加上各種剪枝後時間效率會大大增加，是以搜尋可能反而會更快一些。但是由于我一向不喜歡暴力，是以我強迫自己用第二種方法做。

簡單介紹一下第二種方法：

        1.每棵樹的狀态可用1或0表示，1表示砍掉這棵樹，0表示不砍。那麼這個樹林的情況就可以用二進制數來表達。比如：100101，表示第一棵、第三棵、第六棵會被砍掉（倒過來看）。同時可以将二進制數轉化為十進制數。比如：100101（還是那個數）就是十進制中的37。是以我們任意一個十進制數，都可以用轉為二進制數，進而表達一片樹林的狀态。這樣一來，我們直接可以for循環，從0到2的n次方減1（最多有n棵樹被砍掉）

        2.每一個新的狀況對應着新的凸包，是以要及時更新變量和數組。

        3.凸包要特判一下隻剩下0棵樹和1棵樹的情況，不然會卡住

        4.這道題很容易wa的原因在于——長度要用double類型，千萬别用int！

        5.由于有多組資料，注意要及時更新。總而言之，水題一道。

附上c++代碼：

#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct node
{
	double x,y,v,l;
}a[2100],p[2100],sta[2100];
double multi(node n1,node n2,node no){return (n1.x-no.x)*(n2.y-no.y)-(n2.x-no.x)*(n1.y-no.y);}
double dis(node n1,node n2){return sqrt((n1.x-n2.x)*(n1.x-n2.x)+(n1.y-n2.y)*(n1.y-n2.y));}
int n,dd=0,top=0,nn=0,k=99999999,kk=0;
double ans=0,aans=0;
double sum=0,len=0,s=0;
int maxx;
bool bo[20];
int aa[20];
bool cmp(node n1,node n2)
{
	double t=multi(n1,n2,p[1]);
	if(t==0 && dis(n1,p[1])<dis(n2,p[1]))return true;
	return t>0;
}
void graghm()
{
	top=0;sort(p+2,p+nn+1,cmp);
	for(int i=1;i<=2;i++)sta[++top]=p[i];
	for(int i=3;i<=nn;i++)
	{
		while(top>2 && multi(sta[top],p[i],sta[top-1])<=0)top--;
		sta[++top]=p[i];
	}
}
void make(int d)
{
	memset(bo,true,sizeof(bo));aans=0,s=0;len=0;kk=n;
	int i=1;
	while(d!=0)
	{
		if(d%2==1)bo[i]=false,s+=a[i].l,kk--;
		d/=2;
		i++;
	}
	for(int i=1;i<=n;i++)if(bo[i]==true)aans+=a[i].v;
	nn=0;
	for(int i=1;i<=n;i++)
	{
		if(bo[i]==true)
		{
			p[++nn]=a[i];
			if(p[nn].y<p[1].y || (p[nn].y==p[1].y && p[nn].x<p[1].x))swap(p[1],p[nn]);
		}
	}
	if(kk==1)len=0;
	if(kk>1)
	{
		graghm();
		for(int i=2;i<=top;i++)len+=dis(sta[i],sta[i-1]);
		len+=dis(sta[1],sta[top]);
	}
}
int main()
{
	int t=0;
	while(scanf("%d",&n)!=EOF)
	{
		if(n==0)break;t++;
		ans=0;k=999999999;dd=0;
		for(int i=1;i<=n;i++)
		{
			scanf("%lf%lf%lf%lf",&a[i].x,&a[i].y,&a[i].v,&a[i].l);
		}
		maxx=(1<<n)-1;
		for(int i=0;i<maxx;i++)
		{
			make(i);
			if((ans<aans && s-len>=0) || (ans==aans && kk<k))
			{
				ans=aans;sum=s-len;dd=0;k=kk;
				for(int j=1;j<=n;j++)if(!bo[j])aa[++dd]=j;
			}
		}
		printf("Forest %d\n",t);
		printf("Cut these trees: ");for(int i=1;i<=dd;i++)printf("%d ",aa[i]);
		printf("\nExtra wood: %.2f\n\n",sum);
	}
	return 0;
}
           

如果還有疑問，歡迎向我的郵箱提問——[email protected]，我都樂意回答的哦~