hdu2955 Robberies

題意：某人想去搶銀行，他評估了n個銀行：有多少錢，和搶劫被抓的機率。給定一個不安全的機率p，搶劫時的被抓機率不能超過p，要求求出最多能搶劫的錢數。一開始我也以為機率隻有兩位小數，将它們放大100倍，用機率作重量，錢作為價值。後來錯了，看了别人的題解才知道，将銀行的錢看作重量，安全機率作為價值。

#include<iostream>
#define Max(a,b) ((a)>(b)?(a):(b))
using namespace std;
float w[101];
int c[101];
float dp[10050];
int main()
{
	int t;//0.96
	cin>>t;//0.98
	while(t--)//0.97
	{			//0.95
		float p;
		int n,v=0;
		fill(dp,dp+10050,0);
		dp[0] = 1;
		cin>>p>>n;
		for(int i=1;i<=n;i++)
		{
			cin>>c[i]>>w[i];
			v+=c[i];
		}
		for(int i=1;i<=n;i++)
		{
			for(int j=v;j>=c[i];j--)
			dp[j] = Max(dp[j],dp[j-c[i]]*(1-w[i]));//dp[i]代表搶劫錢數為i的沒有被抓機率 

//			for(int j=v;j>=0;j--)
//			cout<<dp[j]<<" ";
//			cout<<endl;
		}
		int ans= 1e-10;
		for(int j=v;j>=0;j--)
		{
			if(1-dp[j]<p)//找到第一個小于p的 
			{
				cout<<j<<endl;
				break;
			}
		}
	}
}