题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
这个就看做一个背包问题
背包的容量为总价值的一半,每个物品的价值等于它的重量
那么我们就做一下二进制优化的分组背包,最后检验一下背包的价值是否等于背包的容
量,如果相等的话就是可以分为两半的,不行的话就是不能分为两半
C++ 代码
#include<bits/stdc++.h>
using namespace std;
struct node{
int v;
int w;
};
const int maxn = 1e6+10;
int f[maxn];
vector<node> goods;
int main()
{
int a[7],flag = 0,sum = 0;
while(1)
{
memset(f,0,sizeof(f));
goods.clear();
sum = 0;
flag = 0;
for(int i = 0; i < 6; i++)
{
scanf("%d",&a[i]);
if(a[i]==0) flag++;
sum += a[i]*(i+1);
}
if(flag==6) return 0;
if(sum%2==1)
{
puts("Can't");
continue;
}
else sum/=2;
for(int i = 0; i < 6; i++)
{
int s = 1;
while(a[i]>s)
{
a[i]-=s;
goods.push_back({s*(i+1),(i+1)*s}); // 价值等于重量
s*=2;
}
if(a[i]>0) goods.push_back({a[i]*(i+1),a[i]*(i+1)});
}
for(int i = 0; i < goods.size();i++)
{
for(int j = sum; j >= goods[i].w; j--)
{
f[j] = max(f[j],f[j-goods[i].w] + goods[i].v);
}
}
f[sum]==sum?puts("Can"):puts("Can't");
}
return 0;
}