tyvj 1194 划分大理石(多重背包)

解题思路

　　二进制优化多重背包裸题。

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#include<vector>

using namespace std;

const int MAXN = 120005;

inline int rd(){

	int x=0,f=1;char ch=getchar();

	while(!isdigit(ch)) {f=ch=='-'?0:1;ch=getchar();}

	while(isdigit(ch))  {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}

	return f?x:-x;

}

int sum,f[MAXN];

vector<int> v;

int main(){

	while(1){

		int x;memset(f,0,sizeof(f));f[0]=1;v.clear();sum=0;

		for(int i=1;i<=6;i++){

			x=rd();sum+=i*x;

			for(int j=1;j<=x;j<<=1)

				v.push_back(i*j),x-=j;

			if(x) v.push_back(i*x);

		}

		if(!sum) break;

		int Max=0;if((sum&1)) {puts("Can't");continue;}

		for(int i=0;i<v.size();i++){

			Max+=v[i];Max=min(Max,sum);

			for(int j=Max;j>=v[i];j--)

				f[j]|=f[j-v[i]];

		}

		if(f[sum/2]) puts("Can");

		else puts("Can't");

	}

	return 0;

}

巴特西

tyvj 1194 划分大理石(多重背包)

解题思路

代码

最新文章

热门文章