Divide （HG 2008.10.1 T2）
hicc0305
2018-10-01 14:59:13
数据范围是：n<=32, 额外的附加点：n<=5000
显然这题一看就让人想到背包啊。。
然后，统计一下sum，如果是奇数直接输出Can't，偶数的话就sum除以2，看能不能刚好填满。
暴力多重背包就不说了。
然后二进制优化多重背包，可以拿100
那么其他20分呢？
这个显然不用多重背包，毕竟只有能不能到达的状态。可以用f[i][j]表示现在用第i种物品，放满j最多还剩多少个第i种物品。转移就是先全部赋值-1,如果f[i-1][j]>=0,也就是j这个状态已经能达到了，那么f[i][j]=a[i];如果f[i-1][j]<0,f[i][j]=f[i][j-i]-1,什么意思呢，就是从j-i转移过来，然后用掉了一个i物品，所以是f[i][j-i]-1;当然，当i>j时，是不能转移的。然后显然第一位是能去掉的。。
代码如下：
```
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,cnt=0;
int a[10],f[100100];
int read()
{
int x=0,w=0; char c=0;
while(c<'0'||c>'9') {w|=c=='-';c=getchar();}
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
return w?-x:x;
}
int main()
{
n=read();
while(n--)
{
memset(f,0,sizeof(f));
cnt=0;
int sum=0;
for(int i=1;i<=6;i++)
a[i]=read(),sum+=i*a[i];
if(sum%2==1)
{
printf("Can't be divided.\n");
continue;
}
sum/=2,f[0]=0;
for(int i=1;i<=sum;i++)
f[i]=-1;
for(int i=1;i<=6;i++)
for(int j=0;j<=sum;j++)
{
if(f[j]>=0) f[j]=a[i];
else if(i<=j) f[j]=f[j-i]-1;
else f[j]=-1;
}
if(f[sum]>=0) printf("Can be divided.\n");
else printf("Can't be divided.\n");
}
return 0;
}
```