読者です 読者をやめる 読者になる 読者になる

AOJ Problem 2069 : Greedy, Greedy.

404 Not Found

使える通貨の種類が与えられるので、それを使って支払えるものの判定をする。立体数とかどうでもいい。

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