Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
终于AC了,囧rz................#include<stdio.h> #define wds -9999999 int f[120005]; int V; int max(int x,int y){return x>y?x:y;} void ZeroOnePack(int cost,int weight) { int v; for(v=V;v>=cost;v--) f[v]=max(f[v],f[v-cost]+weight); } void CompletePack(int cost,int weight) { int v; for(v=cost;v<=V;v++) f[v]=max(f[v],f[v-cost]+weight); } void MultiplePack(int cost,int weight,int mount) { if(cost*mount>=V) { CompletePack(cost,weight); return; } int k=1; while(k<mount) { ZeroOnePack(k*cost,k*weight); mount-=k; k=k*2; } ZeroOnePack(mount*cost,mount*weight); } int main() { // freopen("in.txt","r",stdin); int n[7],i; int num=0; while(scanf("%d%d%d%d%d%d",&n[1],&n[2],&n[3],&n[4],&n[5],&n[6])) { V=0; for(i=1;i<=6;i++) V+=i*n[i]; if(V==0) break; num++; if(V%2!=0) { printf("Collection #%d:\n",num); printf("Can't be divided.\n\n"); continue; } V=V/2; f[0]=0; for(int ii=1;ii<=V;ii++) f[ii]=wds; // else { for(i=1;i<=6;i++) { MultiplePack(i,i,n[i]); } // f[1],f[2],f[3],f[4],f[5],f[6]; if(V==f[V]) { printf("Collection #%d:\n",num); printf("Can be divided.\n\n"); } else { printf("Collection #%d:\n",num); printf("Can't be divided.\n\n"); } } } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator