题意：

两辆车去运一堆货物，货物数量小于等于10，问最少需要几趟能把货物全部运到目的地。

思路：

思路很简单，就是状态压缩成二进制。判断一下每个状态能不能运输。再进行一下DP。

设s[]数组里记录所有能转移的状态。

状态转移方程：f[i|s[j]]=min(f[i|s[j]],f[i]+1)

但是。 实现起来。。求出s[]数组用的方法很重要。。

先是二重循环枚举状态 但是这会超时。。。 竟然卡不过去。。。好失败

然后就想当然地用lowbit写。。。。肯定是WA了。

最后请教了cy才把这道题解了。。。她用了一个小优化。先统计出来1出现在哪里，然后再枚举，效率是会快一些。。

TLE代码：

// by SiriusRen

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

int cases,n,C1,C2,w[11],s[1024],top,f[1024];

int main(){

    scanf("%d",&cases);

    for(int I=1;I<=cases;I++){

        top=0,scanf("%d%d%d",&n,&C1,&C2);

        for(int i=1;i<=n;i++)scanf("%d",&w[i]);

        for(int i=1;i<=(1<<n)-1;i++)

            for(int j=0;j<=i;j++)

                if(i==(i|j)){

                    int tempx=i&j,tempy=i^j,jyx=0,jyy=0;

                    for(int k=1;tempx;k++,tempx/=2)if(tempx&1)jyx+=w[k];

                    for(int k=1;tempy;k++,tempy/=2)if(tempy&1)jyy+=w[k];

                    if((jyx<=C1&&jyy<=C2)){s[top++]=i;break;}

                }

        memset(f,0x3f,sizeof(f)),f[0]=0;

        for(int i=0;i<=(1<<n)-1;i++)

            for(int j=0;j<top;j++)

                if(!(i&s[j]))f[i|s[j]]=min(f[i|s[j]],f[i]+1);

        printf("Scenario #%d:\n%d\n\n",I,f[(1<<n)-1]);

    }

}

AC代码：

// by SiriusRen

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

int cases,n,C1,C2,w[11],s[1024],top,f[1024];

bool judge(int x){

    int q[11],pos=0,sum=0;

    for(int k=1;x;k++,x>>=1)if(x&1)q[++pos]=k,sum+=w[k];

    for(int i=0;i<1<<pos;i++){

        int s=0;

        for(int j=1;j<pos;j++)

            if(i&(1<<j))s+=w[q[j]];

        if((s<=C1&&sum-s<=C2)||(s<=C2&&sum-s<=C1))return 1;

    }

    return 0;

}

int main(){

    scanf("%d",&cases);

    for(int I=1;I<=cases;I++){

        top=0,scanf("%d%d%d",&n,&C1,&C2);

        for(int i=1;i<=n;i++)scanf("%d",&w[i]);

        for(int i=1;i<1<<n;i++)

            if(judge(i))s[top++]=i;

        memset(f,0x3f,sizeof(f)),f[0]=0;

        for(int i=0;i<1<<n;i++)

            for(int j=0;j<top;j++)

                if(!(i&s[j]))f[i|s[j]]=min(f[i|s[j]],f[i]+1);

        printf("Scenario #%d:\n%d\n\n",I,f[(1<<n)-1]);

    }

}