> #include<stdio.h>
> #include<string.h> 
> #include<stdlib.h>
> #include<iostream>
> #include<algorithm>
> #include<cmath> 
> #include<map>
> using namespace std;
> int n,m;
> double eval[4][4000000];
> int  tnum[55],bou,ax[4];
> struct pp
> {
> 	int num[4],id;
> 	double f_value,e_value;
> 	double pri;
> };
> double dp[4000000];
> int p[4000000];
> pp rou[4000000];
> bool cmp(pp x,pp y)
> {
> 	return x.id<y.id;
> }
> pp now,heap[10000000],po,nw,query[100001],there[55];
> int size;
> char ch;
> void heapify(int id)
> {
> 	int l=2*id+1,r=2*id+2,ii=id;
> 	if(l<size&&heap[l].f_value+heap[l].e_value<heap[ii].f_value+heap[ii].e_value)
> 	   ii=l;
>     if(r<size&&heap[r].f_value+heap[r].e_value<heap[ii].f_value+heap[ii].e_value)
>        ii=r;
>     if(ii!=id)
>     {
>     	swap(heap[ii],heap[id]);
>     	heapify(ii);
>     }
> }
> void min_heapify(int id)
> {
> 	int ii=(id-1)/2;
> 	if(id&&heap[ii].f_value+heap[ii].e_value>heap[id].f_value+heap[ii].e_value)
> 	{
> 		swap(heap[ii],heap[id]);
> 		min_heapify(ii);
> 	}
> }
> double astar(pp x)
> {
> 	int id,ip,i,j,s,bou=(x.num[0]+1)*(x.num[1]+1)*(x.num[2]+1)*(x.num[3]+1);
>     for(i=0;i<bou;i++)
>     	dp[i]=(double)100000000.000*(double)100000000.000;
>    	p[0]=0;
>     size=1;
>     memset(heap[0].num,0,sizeof(heap[0].num));
>     heap[0].f_value=0;
>     heap[0].e_value=0;
>     dp[0]=0;
> 	for(i=0;i<4;i++)
>     {
>     	if(heap[0].e_value<eval[i][x.num[i]])
>     	   heap[0].e_value=eval[i][x.num[i]];   
>     }  
>     while(size)
>     {
>     	nw=heap[0];
>     	id=nw.num[0]*(x.num[1]+1)*(x.num[2]+1)*(x.num[3]+1)+nw.num[1]*(x.num[2]+1)*(x.num[3]+1)+nw.num[2]*(x.num[3]+1)+nw.num[3];
>     	heap[0]=heap[size-1];
>     	if(nw.e_value==0)
>     	   return nw.f_value;
> 		size--;
>     	heapify(0);
> 		for(i=0;i<n;i++)
> 		{
>   		    for(j=0;j<4;j++)
>   		    	now.num[j]=min(x.num[j],nw.num[j]+there[i].num[j]);
>  	        ip=now.num[0]*(x.num[1]+1)*(x.num[2]+1)*(x.num[3]+1)+now.num[1]*(x.num[2]+1)*(x.num[3]+1)+now.num[2]*(x.num[3]+1)+now.num[3];
>  	        if(dp[ip]>dp[id]+there[i].pri)
>  	        {
>  	        	now.e_value=0;
>  	        	for(j=0;j<4;j++)
>  	        	{
>  	        		if(now.e_value<eval[j][x.num[j]-now.num[j]])
>  	        		   now.e_value=eval[j][x.num[j]-now.num[j]];
>  	        	}
>  	        	dp[ip]=dp[id]+there[i].pri;
>  	        	now.f_value=dp[ip];
>  	        	p[ip]=i+1;
>  	        	rou[ip]=nw;
>  	        	heap[size++]=now;
>  	        	min_heapify(size-1);
>  	        }
>     	}
>     } 
> }
> int main()
> {
> 	int id,ip,tst=0,i,j,s,op;  
> 	while(scanf("%d",&n)&&n)
> 	{
> 		tst++; 
> 		for(i=0;i<n;i++)
> 		{
> 		   scanf("%d%lf",&there[i].id,&there[i].pri); 
> 		   memset(there[i].num,0,sizeof(there[i].num));
> 		   ch=getchar();
> 		   op=j=0;
> 		   while(ch!='\n')
> 		   { 
> 		   	   if(ch>='a'&&ch<='z')
> 		   	   {
> 				  there[i].num[j]+=op;		   	 
> 			      j=ch-'a';
> 		   	      op=0; 
> 		 	   }
> 		 	   else if(ch>='0'&&ch<='9')
>   	               op=10*op+ch-'0'; 
> 		       ch=getchar();
> 		   } 
> 		   there[i].num[j]+=op;
> 		}
> 		sort(there,there+n,cmp);
> 		memset(ax,0,sizeof(ax));
> 		scanf("%d",&m);
> 		ch=getchar();
>         j=0;		
> 		for(i=0;i<m;i++)
> 		{
> 			ch=getchar();
> 			memset(query[i].num,0,sizeof(query[i].num));
> 			j=op=0;
> 			while(ch!='\n')
> 			{
> 				if(ch>='a'&&ch<='z')
> 				{
> 					query[i].num[j]+=op;
> 					j=ch-'a';
> 				    op=0;
> 				}
> 				else if(ch>='0'&&ch<='9')
> 				    op=10*op+ch-'0';
> 				ch=getchar();
> 			}
> 			query[i].num[j]+=op;
>    		    for(j=0;j<4;j++)
> 		    {
> 		      if(ax[j]<query[i].num[j])
> 		         ax[j]=query[i].num[j];
> 		    }
> 		}   
> 		for(i=0;i<4;i++)
> 		{
> 		  for(j=0;j<=ax[i];j++)
> 		     eval[i][j]=(double)100000000.000*(double)100000000.000;
> 		  eval[i][0]=0.000;
> 		}
> 		for(i=0;i<n;i++)
> 			for(j=0;j<4;j++)
> 			{
> 				for(s=0;s+there[i].num[j]<=ax[j];s++)
> 				{
> 					if(eval[j][s+there[i].num[j]]>eval[j][s]+there[i].pri)
> 					   eval[j][s+there[i].num[j]]=eval[j][s]+there[i].pri;
> 				}
> 			}
> 		for(i=0;i<4;i++)
> 		  for(j=ax[i];j>0;j--)
> 		  {
> 		  	if(eval[i][j-1]>eval[i][j])
> 		  	   eval[i][j-1]=eval[i][j];
> 		  }
> 		for(i=0;i<4;i++)
> 		   nw.num[i]=ax[i];
> 	    printf("Input set #%d:\n",tst);
> 		for(i=0;i<m;i++)
> 		{
> 		    printf("%d:%8.2lf",i+1,astar(query[i]));
> 	        memset(tnum,0,sizeof(tnum));
> 	        now=query[i];
> 			while(true)
> 	        {
> 	        	int ip=now.num[0]*(query[i].num[1]+1)*(query[i].num[2]+1)*(query[i].num[3]+1)+now.num[1]*(query[i].num[2]+1)*(query[i].num[3]+1)+now.num[2]*(query[i].num[3]+1)+now.num[3];
> 	        	if(p[ip]<=0)
> 	        	   break;
> 				tnum[p[ip]-1]++;
> 	        	now=rou[ip];
> 	        }
> 	        for(j=0;j<n;j++)
> 	        {
> 	        	if(tnum[j]>0)
> 	        	{
> 	        		printf(" %d",there[j].id);
> 	        	    if(tnum[j]>1)
> 	        	    	printf("(%d)",tnum[j]);
> 				}
> 	        }
> 	        printf("\n");
> 		}
> 	}
> 	return 0;
> }

恭喜你，你打错了一个字

• Re:气死我了，怎么会WA,，这么优秀的算法。。。 (42) bankrupt 2010-04-23 20:06:12