1203 i need a offer!.cpp

威士忌的HDU题解.大概有260多题的源码。对于学习非常有好处。

//注意特殊数据如
/* 	1 0
	
	0 1
	0 0
	
	0 1
	0 1
*/ 
#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;

struct infor
{
	int ai;
	float bi;
	bool operator < (const infor &t ) const
	{
			return ai<t.ai; 
	}
}msg[1010];
float p1[10010],p2[10010];

int main()
{
	int i,j,k,n,m,cost,cmax;
	double dmin,t;

	while( scanf("%d %d",&n,&m)!=EOF )
	{
		if(n==0 && m==0)
			break;
		memset(p1,0,sizeof(p1));
		memset(p2,0,sizeof(p2));
		for(i=0;i<m;i++)
		{
			scanf("%d %f",&msg[i].ai,&msg[i].bi);
			msg[i].bi=1-msg[i].bi;
		}
		partial_sort(msg,msg+2,msg+m);
		if(msg[0].ai>n)
			dmin=1;
		else
		{
			dmin=p1[ msg[0].ai ]=msg[0].bi;
			k=cmax=msg[0].ai;
			for(i=1;i<m;i++)
			{
				k=cmax;
				for(j=0;j<=k;j++)
				{
					if(p1[j]==0)
						continue;
					cost=j+msg[i].ai;
					if(cost>n)
						break;
					if(cost>cmax)
						cmax=cost;
					p2[cost]=p1[j]*msg[i].bi;
					if(dmin>p2[cost] )
						dmin=p2[cost];
				}
				for(j=0;j<=cmax;j++)
					if(p2[j]!=0)
					{
						p1[j]=p2[j];
						p2[j]=0;
					}
				if(msg[i].ai<=n)
					if(p1[ msg[i].ai ]==0 || p1[ msg[i].ai ]>msg[i].bi )
					{
						p1[ msg[i].ai ]=msg[i].bi;
						if(msg[i].bi<dmin)
							dmin=msg[i].bi;
					}
			}//for
		}//if
		if(n!=0 && m==0)	
			dmin=1;
		printf("%.1f%%\n",100*(1-dmin));
	}
	return 0;
}