hdu2955 Robberies(java)

 1 import java.util.Scanner;
 2 
 3 public class Test1 {
 4 
 5     public static void main(String[] args) {
 6         
 7         double[] dp=new double[10005];
 8         int[] m=new int[105];
 9         double[] p=new double[105];
10         
11         Scanner input=new Scanner(System.in);
12         int t=input.nextInt();
13         int sum,n,i,j;
14         double P;
15         
16         while(t--!=0) {
17             
18             sum=0;
19             P=input.nextDouble();
20             P=1-P;
21             n=input.nextInt();
22             
23             for(i=0;i<n;i++) {
24                 
25                 m[i]=input.nextInt();
26                 p[i]=input.nextDouble();
27                 p[i]=1-p[i];
28                 sum+=m[i];
29                 
30             }
31             
32             dp[0]=1;
33             for(i=0;i<n;i++) {
34                 
35                 for(j=sum;j>=m[i];j--) {
36                     
37                     dp[j]=Math.max(dp[j],dp[j-m[i]]*p[i]);
38                     
39                 }
40             }
41             
42             for(i=sum;i>=0&&dp[i]<P;i--);
43             
44             System.out.println(i);
45             
46             
47         }
48     }
49 }