题意：
两辆车去运一堆货物，货物数量小于等于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:
%d
",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:
%d
",I,f[(1<<n)-1]);
}
}