bzoj3717 [PA2014]Pakowanie

Description

你有n个物品和m个包。物品有重量，且不可被分割；包也有各自的容量。要把所有物品装入包中，至少需要几个包？

Input

第一行两个整数n,m(1<=n<=24,1<=m<=100)，表示物品和包的数量。
第二行有n个整数a[1],a[2],…,a[n] (1<=a[i]<=10^8)，分别表示物品的重量。
第三行有m个整数c[1],c[2],…,c[m] (1<=c[i]<=10^8)，分别表示包的容量。

Output

如果能够装下，输出一个整数表示最少使用包的数目。若不能全部装下，则输出NIE。

Sample Input

4 3

4 2 10 3

11 18 9

Sample Output

2

题解

这个范围一开始不敢状压，结果发现了时限90s..

首先背包按大小排个序，先装大的比较划算。

那就开两个数组，$f[s]$表示$s$时取到最少是多少，$g[s]$表示$s$时对应的最后一个包剩的最后容量。

这样对于每一个状态就可以枚举比它少一位的所有状态。可以用树状数组的那个lowbit求出来(很神奇)，分情况讨论是不是能装下。

这样就可以愉快的转移了，复杂度$O(2^{24} \times 24)$，跑了26秒23333

#include <cstdio>
#include <algorithm>
#include <cstring>
#define lowbit(i) (i&-i)
using namespace std;
bool comp(int a,int b)
{
    return a>b;
}
int f[(1<<24)+10],g[(1<<24)+10],n,m,v[(1<<24)+10],b[1010];
main()
{
    scanf("%d%d",&n,&m);
    for (int i=0;i<n;i++)
        scanf("%d",&v[i]);
    for (int i=n-1;i>=0;i--)
        v[(1<<i)]=v[i];
    for (int i=1;i<=m;i++)
        scanf("%d",&b[i]);
    sort(b+1,b+1+m,comp);
    memset(f,0x3f,sizeof 0);
    f[0]=0,g[0]=-1;
    for (int s=1;s<=(1<<n)-1;s++)
    {
        f[s]=m+1,g[s]=-1;
        int now=s,temp=s;
        while (temp)
        {
            now=s-lowbit(temp);
            if (g[now]>=v[lowbit(temp)] && (f[s]>f[now]||(f[s]==f[now] && g[now]-v[lowbit(temp)]>g[s])))
                f[s]=f[now],g[s]=g[now]-v[lowbit(temp)];
            else if (b[f[now]+1]>=v[lowbit(temp)] && (f[s]>f[now]+1 || (f[now]+1==f[s] && b[f[now]+1]-v[lowbit(temp)]>g[s])))
                f[s]=f[now]+1,g[s]=b[f[now]+1]-v[lowbit(temp)];
            temp-=lowbit(temp);
        }
    }
    if (f[(1<<n)-1]>m)
        puts("NIE");
    else
        printf("%d\n",f[(1<<n)-1]);
}

最大收获：波兰语的“不”是“NIE”。