Luogu P1537 弹珠

Author： YorkWu
发布时间：March 24, 2019
1144 views
No comments
657 words
Categories： OI 题目

[题目链接](https://www.luogu.org/problemnew/show/P1537 "题目链接")

* * *

水背包，$f\[i\]$表示能否凑成$i$价值的物品； 分成两组，及判断$f\[sum/2\]$的情况。

* * *

#### 代码
```cpp
    #include<bits/stdc++.h>
    using namespace std;
    int f[210009],a[7],s,tot;
    int main(){
        while(1){
            tot++;
            s=0;
            for(int i=1;i<=6;i++){
                cin>>a[i];
                s+=a[i]*i;
            }
            if(s==0) break;
            printf("Collection #%d:\n",tot);
            if(s%2==1){
                printf("Can't be divided.\n\n");
                continue;
            }
            f[0]=1;
            for(int i=1;i<=6;i++){
                for(int j=s/2;j>=i;j--){
                    for(int k=1;k<=a[i];k++){
                        if(i*k<=j&&f[j-k*i]==1) f[j]=1;
                    }
                }
            }
            if(f[s/2]==1) printf("Can be divided.\n\n");
            else printf("Can't be divided.\n\n");
            for(int i=1;i<=s/2;i++) f[i]=0;
        }
        return 0;
    }
```

Last modification：March 14, 2020