bzoj 1110: [POI2007]砝码Odw 贪心

第一次见到这个模型.   

首先，不难得出砝码的种类不会超过 $log(10^9)$ 个，然后就不会分析了qaq...  

那么，就说明一共只有 $30$ 多个本质不同的砝码. 

考虑对每个背包进行状态的压缩：写成若干个砝码大小乘积的形式. 

即 $v[i]=w[i]*a+w[i+1]*b+....$   

然后，将所有背包的系数加和 (有点类似于不进位的进制）

因为呢，你发现两个是不能拼成更大的背包的，所以只能在原有的位置上累加. 

根据贪心，我们一定优先装更小的物品. 

如果这一位有值，直接在这一位上拿一个即可，否则就要从高位借一个，然后给之间每一位的系数都累加一下.   

code: 

#include <bits/stdc++.h>
using namespace std;
void setIO(string s)
{
    string in=s+".in";
    freopen(in.c_str(),"r",stdin);
}
int n,m,len,ans;
int bas[52],w[100010],v[100010],c[52];
int main()
{
    // setIO("input");
    int i,j;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;++i)      scanf("%d",&w[i]);
    for(i=1;i<=m;++i)      scanf("%d",&v[i]);
    sort(v+1,v+1+m);
    for(i=1;i<=m;++i)
    {
        if(v[i]>bas[len]) bas[++len]=v[i];
        v[i]=len;
    }
    for(i=1;i<=n;++i)    for(j=len;j;--j) c[j]+=w[i]/bas[j],w[i]%=bas[j];
    for(i=1;i<=m;++i)
    {
        if(c[v[i]]) c[v[i]]--,ans++;
        else
        {
            for(j=v[i];j<=len;++j)
            {
                if(c[j])
                {
                    --c[j];
                    break;
                }
                else
                {
                    c[j]=bas[j+1]/bas[j]-1;
                }
            }
            if(j>len)      break;
            else     ++ans;
        }
    }
    printf("%d\n",ans);
    return 0;
}