AOJ1028:ICPC: Ideal Coin Payment and Change

太郎くんがP円の物を買う。持っている1円〜500円までの硬貨の枚数が与えられた時、支払う枚数＋お釣りの枚数の最小値を求める問題。お釣りは返す枚数が一番少なくなるように返される。

支払う枚数とお釣りの枚数を別々に求める。お釣りの方は貪欲に支払われるので簡単。問題は支払うときの方。
dp[i][j]:i種類目までの硬貨でj円を払う最小の硬貨の枚数
と定義してあげて、（vは硬貨の価値）
dp[i+1][j]=min(dp[i][j-k✕v[i] | 0≦k≦N[i]かつj-k✕v[i]≧0)
である。しかし、これだとN≦1000より間に合わない。ここで、蟻本にも載っている「スライド最小値」を用いる。
b[j]=dp[i][j✕v[i]+a]-j　と定義すると、（0≦a＜v[i]）
dp[i+1][j✕v[i]+a]=min(b[k] | j-N[i]≦k≦j) +j
と表すことが出来る。このminの部分にdequeを用いることで間に合う。

#include <bits/stdc++.h>
using namespace std;
const int kou[]={1,5,10,50,100,500};
int dp[7][700000];
int main(){
    while(true){
        int p;  cin>>p;
        if(p==0)    return 0;
        vector<int> n(6);
        for(int i=0;i<6;i++){
            cin>>n[i];
        }
        for(int i=0;i<7;i++){
            dp[i][0]=0;
            for(int j=1;j<700000;j++)    dp[i][j]=1<<25;
        }
        int end=0;
        for(int i=0;i<6;i++){
            end+=n[i]*kou[i];
            for(int a=0;a<kou[i];a++){
                deque<pair<int,int>> dq;//値、インデックス
                for(int j=0;j*kou[i]+a<=end;j++){
                    int val=dp[i][j*kou[i]+a]-j;
                    while(!dq.empty()&&dq.back().first>=val) dq.pop_back();
                    dq.push_back(make_pair(val,j));
                    dp[i+1][j*kou[i]+a]=dq.front().first+j;
                    while(!dq.empty()&&j-dq.front().second>=n[i])    dq.pop_front();
                }
            }
        }
        int ans=INT_MAX;
        for(int i=p;i<=end;i++){
            int tmp=dp[6][i],v=i-p;
            int tmp2=0;
            for(int j=5;j>=0;j--){
                tmp2+=v/kou[j]; v%=kou[j];
            }
            ans=min(ans,tmp+tmp2);
        }
        cout<<ans<<endl;
    }
}

しばらくはこんな感じでAOJを解き進めつつ、TopCoderやCodeforcesに出て行きたいかな、と思います。