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

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