「AOJ1091～1100」の編集履歴（バックアップ）一覧に戻る

AOJ1091～1100 - (2013/01/24 (木) 16:17:53) のソース

*問い1092　Make KND So Fat
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1092
甘味どころで体重が増えるようにお菓子を買う問題。

解法
範囲が狭いので何も考えない動的計画法で十分解けます。


 #include<stdio.h>
 #include<vector>
 void calc(int s,int d,int m){
 	int memo[310]={0},k,w,p;;
 	std::vector<int> ws[101],ps[101];
 	for(int i=0;i<s;i++){
 		scanf("%d",&k);
 		for(int j=0;j<k;j++){
 			scanf("%d %d",&w,&p);
 			ws[i].push_back(w);
 			ps[i].push_back(p);
 		}
 	}
 	int f,a;
 	for(int i=0;i<d;i++){
 		scanf("%d",&f);
 		for(int j=0;j<ws[f].size();j++){
 			w=ws[f][j];
 			p=ps[f][j];
 			for(int k=m-p;k>=0;k--){
 				if(k!=0&&memo[k]==0)continue;
 				a=memo[k]+w;
 				if(memo[k+p]<a)memo[k+p]=a;
 			}
 		}
 	}
 	int ansP=0,ansW=0;
 	for(int i=0;i<=m;i++){
 		if(ansW<memo[i]){
 			ansW=memo[i];
 			ansP=i;
 		}
 	}
 	printf("%d %d\n",ansW,ansP);
 } 
 
 int main(){
 	int s,d,m;
 	while(scanf("%d",&s)!=EOF){
 		scanf("%d %d",&d,&m);
 		calc(s,d,m);
 	}
 }