BZOJ 1110 POI2007 砝码Odw 贪心

题目大意：给定n个砝码和m个背包，保证对于任意两个砝码都有一个是另一个的正整数倍，求最多拿走多少砝码

http://hzwer.com/4761.html

大概想到了进制拆分但是没想到具体怎么做。。。

我还是太弱了。。。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define M 100100
using namespace std;
int n,m,ans;
int a[M],b[M];
int stack[40],top;
long long digit[40];
int main()
{
	int i,j,k;
	cin>>n>>m;
	for(i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(i=1;i<=m;i++)
		scanf("%d",&b[i]);
	sort(b+1,b+m+1);
	for(i=1;i<=m;i++)
		if(i==1||b[i]!=b[i-1])
			stack[++top]=b[i];
	for(i=1;i<=n;i++)
		for(j=top;j;j--)
			digit[j]+=a[i]/stack[j],a[i]%=stack[j];
	for(j=1,i=1;i<=top;i++)
		for(;j<=m&&b[j]==stack[i];j++)
		{
			if(digit[i])
			{
				++ans;--digit[i];
				continue;
			}
			for(k=i+1;k<=top;k++)
				if(digit[k])
					break;
			if(k==top+1)
			{
				cout<<ans<<endl;
				return 0;
			}
			for(;k>i;k--)
				digit[k]--,digit[k-1]+=stack[k]/stack[k-1];
			++ans;--digit[i];
		}
	cout<<ans<<endl;
	return 0;
}

BZOJ 1110 POI2007 砝码Odw 贪心

原文：http://blog.csdn.net/popoqqq/article/details/44594099