問い1092 Make KND So Fat
解法
範囲が狭いので何も考えない動的計画法で十分解けます。
#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);
}
}
最終更新:2013年01月24日 16:17