AOJ2138: Vending Machine
AOJ 2138: Vending Machine (Summer Camp (Day 2), Tokyo, 13 Sep 2008)
昔DPだろうと思って突撃して死んだ問題。
今もう一度考え直してみたら、ただのBFSだと気付きました。
概要
N < 10種類のコインをそれぞれ高々 t 枚づつ使って k <= 100,000円を支払う。tを最小化せよ。
解法
N種類のコインをそれぞれ高々1枚づつ使う組み合わせは2^N通り。これを辺として、金額を頂点とするグラフ上でBFSする。
O(2^N * k). 最悪ケースで億のオーダになるけど、サーバの速さを信じて送ったらすんなり通った。
遅いけれども、コードが簡潔なので満足。
コード
#include <iostream> #include <queue> #define REP(i,e) for(int i=0;i<(int)(e);i++) using namespace std; const int N=10; const int M=200000; const int inf=1<<20; int e[1<<N]; struct state{ int n,cost; }; int BFS(int n,int dst){ static int cost[M]; REP(i,dst+1) cost[i]=inf; queue<state> qu; for(qu.push((state){0,0});!qu.empty();qu.pop()){ state s=qu.front(); if(cost[s.n]!=inf) continue; cost[s.n]=s.cost; REP(i,n) if(s.n+e[i]<=dst && cost[s.n+e[i]]==inf) qu.push((state){s.n+e[i],s.cost+1}); } return cost[dst]; } main(){ int n,k; while(cin >> n >> k && n|k){ int v[N]; REP(i,n) cin >> v[i]; REP(i,1<<n){ int cnt=0; REP(j,n) if(i&(1<<j)) cnt+=v[j]; e[i]=cnt; } cout << BFS(1<<n,k) << endl; } }