bzoj 3717 [PA2014]Pakowanie

bzoj 3717 [PA2014]Pakowanie

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

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

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

Sample Input 4 3 4 2 10 3 11 18 9 Sample Output 2 HINT

Source 鸣谢Jcvb

我也真是sb 说着物品不能拆 我tm都给拆开了 wa死

背包贪心从大到小排序

设dp[s]表示s状态下至少要用几个背包 dp1[s]表示s状态使用当前背包用量最小是多少

直接n*2^n做即可

网上说要常数优化 我随便写写就过了..

#include#include#include#includeusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(!isdigit(ch)) {if (ch=='-') f=-1;ch=gc();} while(isdigit(ch)) x=x*10+ch-'0',ch=gc(); return x*f;}inline bool cmp(const int &a,const int &b){return a>b;}int dp[(1<<24)+10],dp1[(1<<24)+10],n,m,a[(1<<24)+10],c[110];int main(){ freopen("bzoj3717.in","r",stdin); n=read();m=read(); for (int i=0;i(c[dp[s1]]-dp1[s1])){ if (c[dp[s1]+1]dp[s1]+1){ dp[s]=dp[s1]+1;dp1[s]=a[i]; }else if (dp[s]==dp[s1]+1){ dp1[s]=min(dp1[s],a[i]); } }else{ if (dp[s]>dp[s1]){ dp[s]=dp[s1];dp1[s]=dp1[s1]+a[i]; }else if (dp[s]==dp[s1]){ dp1[s]=min(dp1[s],dp1[s1]+a[i]); } } } }if (dp[S]>m) puts("NIE");else printf("%d\n",dp[S]); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。