「AOJ1091~1100」の編集履歴(バックアップ)一覧はこちら

AOJ1091~1100」の最新版変更点

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

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

-*問い1091 Make KND So Fat
+*問い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);
  	}
  }