[POI2004] PRZ - 状压dp

很简单的子集枚举状压dp

这个 (j-1)&i 的子集枚举是真的骚气

#include <bits/stdc++.h>
using namespace std; int W,n,t[20],w[20],st[99999],sw[99999],f[99999]; int main() {
cin>>W>>n;
for(int i=1;i<=n;i++) cin>>t[i]>>w[i];
for(int i=0;i<1<<n;i++) {
for(int j=1;j<=n;j++) {
if(i&(1<<(j-1))) st[i]=max(st[i],t[j]),sw[i]+=w[j];
}
}
memset(f,0x3f,sizeof f);
f[0]=0;
for(int i=1;i<1<<n;i++) {
for(int j=i;j;j=(j-1)&i) {
if(sw[j]<=W) f[i]=min(f[i],f[i^j]+st[j]);
}
}
cout<<f[(1<<n)-1]<<endl;
}
上一篇:MySQL中You can't specify target table for update in FROM clause异常


下一篇:DNS解析过程详解(转载)