PKU Judge Online 3085 Quick Change

■3085 Quick Change

□Problem
￠25,￠10,￠5,￠1の硬貨がある．￠nを最も硬貨が少なくなるように表せ．

□Solution
典型的な動的計画法．
dp[i][n]をi-1までの硬貨を使って，￠nを表す最小枚数とすると，
dp[i+1][n]=min{dp[i][n], dp[i][n-cent_i+1]+1}
ここで，cent_iは硬貨のiの価値．
dp[i][n]はnに初期化しておく．

□Code

view plainprint?

1. package p3085;  
2.   
3. import java.util.*;  
4. import java.lang.*;  
5. import java.math.*;  
6. import java.io.*;  
7.   
8. import static java.lang.Math.*;  
9. import static java.util.Arrays.*;  
10.   
11. // AC  
12. public class Main{  
13.   
14.     Scanner sc=new Scanner(System.in);  
15.   
16.     final int INF=Integer.MAX_VALUE;  
17.     final double EPS=1e-9;  
18.   
19.     void run(){  
20.         int[] cents={25, 10, 5, 1};  
21.         int n=sc.nextInt();  
22.         for(int k=1; k<=n; k++){  
23.             int c=sc.nextInt();  
24.             int[] a=new int[c+1];  
25.             for(int i=0; i<=c; i++)  
26.                 a[i]=i;  
27.             int[] b=new int[c+1];  
28.             for(int j=0; j<4; j++){  
29.                 for(int i=cents[j]; i<=c; i++){  
30.                     int s=i-cents[j];  
31.                     if(a[s]+1<=a[i]){  
32.                         a[i]=a[s]+1;  
33.                         b[i]=j;  
34.                     }  
35.                 }  
36.             }  
37.             int[] count=new int[4];  
38.             for(;;){  
39.                 count[b[c]]++;  
40.                 c-=cents[b[c]];  
41.                 if(c==0)  
42.                     break;  
43.             }  
44.             println(k+" "+count[0]+" QUARTER(S), "+count[1]+" DIME(S), "  
45.                     +count[2]+" NICKEL(S), "+count[3]+" PENNY(S)");  
46.         }  
47.     }  
48.   
49.     void print(String s){  
50.         System.out.print(s);  
51.     }  
52.   
53.     void println(String s){  
54.         System.out.println(s);  
55.     }  
56.   
57.     public static void main(String[] args){  
58.         // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
59.         new Main().run();  
60.     }  
61. }  

package p3085;

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

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

// AC
public class Main{

    Scanner sc=new Scanner(System.in);

    final int INF=Integer.MAX_VALUE;
    final double EPS=1e-9;

    void run(){
        int[] cents={25, 10, 5, 1};
        int n=sc.nextInt();
        for(int k=1; k<=n; k++){
            int c=sc.nextInt();
            int[] a=new int[c+1];
            for(int i=0; i<=c; i++)
                a[i]=i;
            int[] b=new int[c+1];
            for(int j=0; j<4; j++){
                for(int i=cents[j]; i<=c; i++){
                    int s=i-cents[j];
                    if(a[s]+1<=a[i]){
                        a[i]=a[s]+1;
                        b[i]=j;
                    }
                }
            }
            int[] count=new int[4];
            for(;;){
                count[b[c]]++;
                c-=cents[b[c]];
                if(c==0)
                    break;
            }
            println(k+" "+count[0]+" QUARTER(S), "+count[1]+" DIME(S), "
                    +count[2]+" NICKEL(S), "+count[3]+" PENNY(S)");
        }
    }

    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();
    }
}