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 |
多重背包+dp (附代码)#include "stdio.h" #include "memory.h" int result [3][10000*6+1]; int main(void) { int i,sum=0,con=0,j,l,flag=0,temp,k,count[2],front,last; int a[6]; while(++con) { flag=0; sum=0; for(i=0;i!=6;++i) { scanf("%d",a+i); if(a[i]!=0) flag=1; sum+=a[i]*(i+1); } if(flag==0) return 0; if(sum%2==1) { printf("Collection #%d:\nCan't be divided.\n\n",con);continue;} sum/=2; memset(result[2],0,sizeof(int)*60001); result[2][0]=1; result[0][0]=0; front=1;last=0; count[0]=1; count[1]=0; for(i=6;i!=0;--i) { for(j=a[i-1];j>0;--j) { if(front==1){front=0;last=1;} else {front=1;last=0;} count[last]=0; for(k=count[front]-1;k>=0;--k) { temp=result[front][k]+i; if(temp==sum) {result[2][sum]=1; goto lo;} if(temp<sum&&result[2][temp]!=1) { result[2][temp]=1; result[last][count[last]++]=temp; } } } count[last]=0; for(j=0;j<=sum;++j) { if(result[2][j]) result[last][count[last]++]=j; } } lo: if(result[2][sum]==1) printf("Collection #%d:\nCan be divided.\n\n",con); else printf("Collection #%d:\nCan't be divided.\n\n",con); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator