題面
狀壓dp
枚舉一個狀態的子集

#include<iostream> #include<cstdio> #include<cstring> using namespace std; int W,n; int t[20],w[20]; int sum[(1<<16)+5],ti[(1<<16)+5]; int f[(1<<16)+5]; inline int read() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar();}while(ch>='0'&&ch<='9'){ x=x*10+ch-'0'; ch=getchar(); }return x; } void get(int x) {for(int i=1;i<=n;i++)if((1<<i-1)&x) sum[x]+=w[i],ti[x]=max(ti[x],t[i]); } int main() {//freopen("in.txt","r",stdin);memset(f,0xf,sizeof(f));W=read(); n=read();for(int i=1;i<=n;i++) t[i]=read(),w[i]=read();for(int i=0;i<(1<<n);i++) get(i);//cout<<sum[(1<<n)-1]<<endl;f[0]=0;for(int i=1;i<(1<<n);i++)for(int j=i;j;j=(j-1)&i)//枚舉子集if(sum[j]<=W)f[i]=min(f[i],f[i^j]+ti[j]);printf("%d\n",f[(1<<n)-1]);//while(1);return 0; }

轉載于:https://www.cnblogs.com/hunterxhunterl/p/7780653.html

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的bzoj2073的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。