Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:01背包部分由缺陷

Posted by pipipapasha at 2023-10-14 23:47:54 on Problem 1014
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator