使える通貨の種類が与えられるので、それを使って支払えるものの判定をする。立体数とかどうでもいい。
Cannot pay some amountの判定
使える通貨の種類に"1"が無い。(1が無いと入力に無い素数とか絶対払えない。逆に1があれば何でも払おうと思えば払える)
OK , Cannot use greedy algorithm の判定
『使った回数が最小になるように最適に選んだコイン < 貪欲法で求めたコイン』ならCannot use greedy algorithmだと考えた。
自分の解法としては、
幅優先探索で50000(ci<1000 n≦50だから)までの価格に対しての最小のコイン数求める + 貪欲法と照らし合せる。みたいな感じ。力任せでやや遅い。これでも効率化した。
(てか、書いてて気づいた。ci<1000なら999*50でいい・・・)
#include <iostream> #include <vector> #include <algorithm> #include <queue> #include <iostream> #include <cstring> using namespace std; typedef pair<int,int> NODE; #define sum first #define depth second int main(){ int n; int count=0; unsigned int memo[50001]; while(cin >> n, n){ cout << "Case #" << ++count << ": "; bool cant = true; vector<int> data(n); int maxPrice = 0; for(int i=0;i<n;i++){ cin >> data[i]; maxPrice += data[i]; if(data[i]==1)cant=false; } if(cant){ cout << "Cannot pay some amount" << endl; continue; } sort(data.begin(),data.end(),greater<int>()); queue<NODE> Q; memset(memo,~0,50001*4); memo[0] = 0; NODE p = make_pair(0,0); Q.push(p); while(Q.size()){ NODE q = Q.front();Q.pop(); for(int i=0;i<n;i++){ NODE next; next.sum = q.sum + data[i]; next.depth = q.depth + 1; if(next.sum > 50000)continue; //if(next.depth >= r )continue; if((unsigned)next.depth >= memo[next.sum])continue; Q.push(next); memo[next.sum] = next.depth; } } for(int price=1;price<=maxPrice;price++){ int t = price,r=0; for(int i=0;i<n;){ if(t >= data[i]){ t-=data[i]; r++; }else{ i++; } } if(r>memo[price])cant = true; } cout << (cant?"Cannot use greedy algorithm":"OK") << endl; } }