HDOJ2955 Robberies(01背包，概率)

http://acm.hdu.edu.cn/showproblem.php?pid=2955
这道DP题WA了。
今天看了一下，WA在了double max(int x,int y)上，x和y都应该是double 类型才对啊，糊涂了。

double max(int x,int y){
   return x>y?x:y;}for(j=1;j<=N;j++)for(i=sum;i>=0;--i)dp[i]=max(dp[i],dp[i-Mj[i]]*Pj[j]); 

下面是AC代码：

#include<iostream>
#include<cstdio>
#include<string.h>
#include<algorithm>
using namespace std;
int T,N,Mj[101]; //T个case,P是临界概论，Mj是每个case中银行的价值
double P,Pj[101],dp[110];   //N是每个case中银行的个数,Pj是每个银行被捕的概率
double sum=0;
double max(double x,double y){
   return x>y?x:y;}int main(){memset(Mj,0,sizeof(Mj));memset(Pj,0,sizeof(Pj));memset(dp,0,sizeof(dp));cin>>T;int i,j;while(T--){cin>>P>>N;P=1-P;for(i=1;i<=N;i++){cin>>Mj[i]>>Pj[i];sum+=Mj[i];Pj[i]=1-Pj[i];}dp[0]=1; //dp表示概率，d[0]什么都没偷，被捕概率0，及成功逃跑为1for(i=1;i<=N;i++)for(j=sum;j>=Mj[i];j--)dp[j]=max(dp[j],dp[j-Mj[i]]*Pj[i]); //第i个银行偷for(i=sum;i>=0;i--)      //或不偷能逃跑的概率if(dp[i]>=P){cout<<i<<endl;break;}}
return 0;
}