codechef December Challenge 2012 Pizza Delivery 完全背包求最小值 这道很重
Pizza Delivery

Problem code: DBOY

#include<stdio.h>#include<string.h>struct haha{int val;int vol;}k[505];int n;int bag[1005];void _bag(){ int i,j,v=1000;for(i=1;i<=v;i++)bag[i]=999999999;bag[0]=0; for(i=0;i<n;i++) { for(j=k[i].vol;j<=v;j++) { bag[j]=(bag[j-k[i].vol]+k[i].val)<bag[j]?(bag[j-k[i].vol]+k[i].val):bag[j]; } }}int main(){int cas,i,j,h[505];int rem[1005];int num;scanf("%d",&cas);while(cas--){memset(rem,0,sizeof(rem)); scanf("%d",&n);for(i=0;i<n;i++){scanf("%d",&num);rem[num*2]++;}for(i=0;i<n;i++){scanf("%d",&k[i].vol);k[i].val=1;}int ans=0;_bag();//只要调用一次 注意 for(i=0;i<=1000;i+=2)if(rem[i]){ ans+=bag[i]*rem[i];}printf("%d\n",ans);}return 0;}