Aizu Online Judge 0154 Sum of Cards

■0154 Sum of Cards

動的計画法による解法．

dp[i]=総和がiとなるカードの組み合わせ
とすればよい．更新方法は↓参照．

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. import java.io.*;  
5.   
6. import static java.lang.Math.*;  
7. import static java.util.Arrays.*;  
8.   
9. public class Main{  
10.   
11.  Scanner sc=new Scanner(System.in);  
12.   
13.  int INF=1<<28;  
14.  double EPS=1e-9;  
15.   
16.  int m, g;  
17.  int[] a, b, n;  
18.   
19.  void run(){  
20.   for(;;){  
21.    m=sc.nextInt();  
22.    if(m==0){  
23.     break;  
24.    }  
25.    a=new int[m];  
26.    b=new int[m];  
27.    for(int i=0; i<m; i++){  
28.     a[i]=sc.nextInt();  
29.     b[i]=sc.nextInt();  
30.    }  
31.    g=sc.nextInt();  
32.    n=new int[g];  
33.    for(int i=0; i<g; i++){  
34.     n[i]=sc.nextInt();  
35.    }  
36.    solve();  
37.   }  
38.  }  
39.   
40.  void solve(){  
41.   int max=1001;  
42.   int[] dp=new int[max];  
43.   int[] dp2=new int[max];  
44.   dp[0]=1;  
45.   for(int j=0; j<m; j++){  
46.    System.arraycopy(dp, 0, dp2, 0, max);  
47.    for(int i=0; i<b[j]; i++){  
48.     for(int k=max-a[j]*(i+1)-1; k>=0; k--){  
49.      dp[k+a[j]*(i+1)]+=dp2[k];  
50.     }  
51.    }  
52.   }  
53.   for(int i=0; i<g; i++){  
54.    println(""+dp[n[i]]);  
55.   }  
56.  }  
57.   
58.  void debug(Object... os){  
59.   System.err.println(Arrays.deepToString(os));  
60.  }  
61.   
62.  void print(String s){  
63.   System.out.print(s);  
64.  }  
65.   
66.  void println(String s){  
67.   System.out.println(s);  
68.  }  
69.   
70.  public static void main(String[] args){  
71.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
72.   new Main().run();  
73.  }  
74. }  

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 int m, g;
 int[] a, b, n;

 void run(){
  for(;;){
   m=sc.nextInt();
   if(m==0){
    break;
   }
   a=new int[m];
   b=new int[m];
   for(int i=0; i<m; i++){
    a[i]=sc.nextInt();
    b[i]=sc.nextInt();
   }
   g=sc.nextInt();
   n=new int[g];
   for(int i=0; i<g; i++){
    n[i]=sc.nextInt();
   }
   solve();
  }
 }

 void solve(){
  int max=1001;
  int[] dp=new int[max];
  int[] dp2=new int[max];
  dp[0]=1;
  for(int j=0; j<m; j++){
   System.arraycopy(dp, 0, dp2, 0, max);
   for(int i=0; i<b[j]; i++){
    for(int k=max-a[j]*(i+1)-1; k>=0; k--){
     dp[k+a[j]*(i+1)]+=dp2[k];
    }
   }
  }
  for(int i=0; i<g; i++){
   println(""+dp[n[i]]);
  }
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}