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 |
Re:01背包部分由缺陷In Reply To:Re:01背包部分由缺陷 Posted by:witstorm at 2017-11-24 20:27:20 #include<stdio.h> bool*F; int v,x,I,y,a[6],V,c=0,i,j,k; int main() { while(1){ y=V=0; for(i=0;i<6;i++){scanf("%d",a+i);V+=a[i]*(i+1);} if(!V)break; if(V%2!=0||((V/=2)%2&&!a[0]&&!a[2]&&!a[4]))goto l; if(a[0]>4){y=1;goto l;} F=new bool[V+1](); for(i=0;i<=a[0];i++)F[i]=1; v=a[0]; for(i=1;i<=4;i++){ v=(x=v+a[i]*(i+1))>V?V:x; I=i+1; for(j=v;j>=0;j--){ x=(x=j/I)<a[i]?x:a[i]; for(k=1;k<=x;k++)if(F[j-k*I])F[j]=1; if(F[V]){y=1;goto l;} } } x=(x=V/6)<a[5]?x:a[5]; for(k=1;k<=x;k++)if(F[V-k*6]){y=1;break;} l:printf("Collection #%d:\nCan%s be divided.\n\n",++c,y?"":"'t"); delete[] F; } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator