「AOJ201～210」の編集履歴（バックアップ）一覧はこちら

AOJ201～210 - (2011/09/02 (金) 10:14:37) の１つ前との変更点

追加された行は緑色になります。

削除された行は赤色になります。

*0201　Wrought Gold Master
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0201

解法
アイテムを一つずつ確かめて、連金で安くなるならその値段に改定します。
改定した値段で更に調べなおして、値段が改定できなくなるまでループし続ければ答えがも止まります。
非常に短いコードで実装してる方もいるのでもっと賢い方法があるかもしれません。



 #include<iostream>
 #include<map>
 #include<string>
 #include<vector>
 using namespace std;
 void setData(int n){	
	map<string,int> items;
	map<string,vector<string> > process;
	map<string,int>::iterator itemIt;
	vector<string>::iterator processIt,end;
	int Count=1,value,m,k,sum;
	string name,item;	
	for(int i=0;i<n;i++){
		std::cin>>name>>value;
		items[name]=value;
	}
	std::cin>>m;
	for(int i=0;i<m;i++){
		std::cin>>name>>k;
		for(int i=0;i<k;i++){
			cin>>item;
			process[name].push_back(item);
		}
	}
	cin>>name;
	while(Count>0){
		Count=0;
		itemIt=items.begin();
		while(itemIt!=items.end()){
			sum=0;
			if(process.find((*itemIt).first)!=process.end()){
				processIt=process[(*itemIt).first].begin();
				end=process[(*itemIt).first].end();
				while(processIt!=end){
					sum+=items[*processIt];
					processIt++;
				}
				if(sum<(*itemIt).second){
					items[(*itemIt).first]=sum;
					Count++;
				}
			}
			itemIt++;
		}
	}
	cout<<items[name]<<"\n";
 }
 int main(){
	int n;
	while(scanf("%d",&n),n>0){
		setData(n);
	}
 }

*0201　Wrought Gold Master
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0201

解法
アイテムを一つずつ確かめて、連金で安くなるならその値段に改定します。
改定した値段で更に調べなおして、値段が改定できなくなるまでループし続ければ答えがもとまります。
非常に短いコードで実装してる方もいるのでもっと賢い方法があるかもしれません。



 #include<iostream>
 #include<map>
 #include<string>
 #include<vector>
 using namespace std;
 void setData(int n){	
	map<string,int> items;
	map<string,vector<string> > process;
	map<string,int>::iterator itemIt;
	vector<string>::iterator processIt,end;
	int Count=1,value,m,k,sum;
	string name,item;	
	for(int i=0;i<n;i++){
		std::cin>>name>>value;
		items[name]=value;
	}
	std::cin>>m;
	for(int i=0;i<m;i++){
		std::cin>>name>>k;
		for(int i=0;i<k;i++){
			cin>>item;
			process[name].push_back(item);
		}
	}
	cin>>name;
	while(Count>0){
		Count=0;
		itemIt=items.begin();
		while(itemIt!=items.end()){
			sum=0;
			if(process.find((*itemIt).first)!=process.end()){
				processIt=process[(*itemIt).first].begin();
				end=process[(*itemIt).first].end();
				while(processIt!=end){
					sum+=items[*processIt];
					processIt++;
				}
				if(sum<(*itemIt).second){
					items[(*itemIt).first]=sum;
					Count++;
				}
			}
			itemIt++;
		}
	}
	cout<<items[name]<<"\n";
 }
 int main(){
	int n;
	while(scanf("%d",&n),n>0){
		setData(n);
	}
 }