hdu-1203 I Need a Offer

这个题耽误了很长时间，开始一直没有理解清题意，下午上课的时候好好的想了想，分析样例，最终被我找出了规律，加油！吖飒~~~~

只要专注没有不可以！！！！

截至下午，DP这章已经结束啦 。大致地了解了动态规划的一些做题规律。DP必须举一反三，深入了解DP的思想，这事是做这些题的最大感触。加油加油、、、、、

题意：

有n个学校，给定的申请资金内，被录取的最大概率。

分析：

申请n个学校，被录取的概率W是P(W)=1-P(1)*P(2)*....*P(n)【概率论课上刚学的，嘿嘿 学了很有用呀】

于是，所求的最大概率就可以 转化成 求不能被录取的最小概率E。P(W)=1-P(E)

状态转移方程式：dp[j]=min(dp[j],dp[j-N[i].p]*N[i].g);【dp[j]表示j元的申请费用不能被录取的最小概率，p申请费，g不被录取的概率】

注意，有可能出现资金不够用的情况

代码：

#include<iostream>
#include<stdio.h>
using namespace std;
#define min(a,b) ((a)>(b))?(b):(a)
#define max(a,b) ((a)>(b))?(a):(b)
struct info
{
	int p;//费用
	float g;//概率
}N[1001];//学校
float dp[10001];//金额为j时的最大概率
int main()
{
	int m,n;
	while(cin>>m>>n&&(m+n)!=0)//n个学校
	{
		int i,j;
		float Max=0;
		for(i=0;i<n;i++)
		{
			cin>>N[i].p>>N[i].g;
			Max=max(Max,N[i].g);
			N[i].g=1-N[i].g;
		}
		float MAX2=1;
		for(i=0;i<=m;i++) dp[i]=1;
		for(i=0;i<n;i++)
		{
			for(j=m;j>=N[i].p;j--)
			{
				dp[j]=min(dp[j],dp[j-N[i].p]*N[i].g);
				MAX2=min(MAX2,dp[j]);
			}
		}
		if(MAX2==1) Max=0.0;//资金不能申请任意学校
		else if(Max<1-MAX2) 
		Max=(1-MAX2)*100;
		else Max*=100;
		printf("%.1f%%\n",Max);
	}
	return 0;
}