【BZOJ2073】[POI2004]PRZ 状压DP
DP 状压
2023-09-11 14:15:27 时间
【BZOJ2073】[POI2004]PRZ
Description
一只队伍在爬山时碰到了雪崩,他们在逃跑时遇到了一座桥,他们要尽快的过桥. 桥已经很旧了, 所以它不能承受太重的东西. 任何时候队伍在桥上的人都不能超过一定的限制. 所以这只队伍过桥时只能分批过,当一组全部过去时,下一组才能接着过. 队伍里每个人过桥都需要特定的时间,当一批队员过桥时时间应该算走得最慢的那一个,每个人也有特定的重量,我们想知道如何分批过桥能使总时间最少.
Input
第一行两个数: w – 桥能承受的最大重量(100 <= w <= 400) 和 n – 队员总数(1 <= n <= 16). 接下来n 行每行两个数分别表示: t – 该队员过桥所需时间(1 <= t <= 50) 和 w – 该队员的重量(10 <= w <= 100).
Output
输出一个数表示最少的过桥时间.
Sample Input
100 3
24 60
10 40
18 50
24 60
10 40
18 50
Sample Output
42
题解:状压DP,刷水有益健康。
#include <cstdio> #include <cstring> #include <iostream> using namespace std; int m,n,tot; int f[1<<16],v[1<<16],u[1<<16]; int t[20],w[20]; int main() { scanf("%d%d",&m,&n); memset(f,0x3f,sizeof(f)); int i,j; for(i=1;i<=n;i++) scanf("%d%d",&t[i],&w[i]); for(i=1;i<1<<n;i++) { int x=i,y=1,nw=0,nt=0; while(x) { if(x&1) nw+=w[y],nt=max(nt,t[y]); x>>=1,y++; } if(nw<=m) v[++tot]=i,u[tot]=nt; } f[0]=0; for(i=1;i<1<<n;i++) { for(j=1;v[j]<=i&&j<=tot;j++) { if((i&v[j])==v[j]) f[i]=min(f[i],f[i-v[j]]+u[j]); } } printf("%d",f[(1<<n)-1]); return 0; }
相关文章
- hdu1074 状态压缩dp+记录方案
- hdu1025 Constructing Roads In JGShining's Kingdom(二分+dp)
- 【状态设计优化DP】Atcoder Beginner Contest E - Work or Rest
- 【POJ 3071】 Football(DP)
- BZOJ 1605 [Usaco2008 Open]Crisis on the Farm 牧场危机 DP
- 【BZOJ1912】[Apio2010]patrol 巡逻 树形DP
- 【BZOJ1097】[POI2007]旅游景点atr 最短路+状压DP
- 【BZOJ3450】Tyvj1952 Easy 期望DP
- CodeForces 935E Fafa and Ancient Mathematics (树形DP)
- BZOJ 1444 [Jsoi2009]有趣的游戏 (AC自动机 + 概率DP + Gauss)
- BZOJ 1026 [SCOI2009]windy数 (数位DP)
- BZOJ 1087 [SCOI2005]互不侵犯King (状压DP)
- HDU 6125 Free from square (状压DP+背包)
- HDU 4114 Disney's FastPass (状压DP)
- POJ 1795 DNA Laboratory (贪心+状压DP)
- HDU 4599 Dice (概率DP+数学+快速幂)
- HDU 3366 Passage (概率DP)
- UVa 1220 Party at Hali-Bula (树形DP,最大独立集)
- HDU 2089 不要62 (递推+暴力或者数位DP)
- BZOJ 1087 SCOI2005 互不侵犯King 状压DP
- HDU2089 ------不要62(数位dp)
- dp协议学习----1、sst协议学习
- UVA - 825Walking on the Safe Side(dp)
- 【bzoj2669】[cqoi2012]局部极小值 容斥原理+状压dp
- 【bzoj2004】[Hnoi2010]Bus 公交线路 状压dp+矩阵乘法
- 【bzoj4987】Tree 树形背包dp
- 【bzoj3143】[Hnoi2013]游走 期望dp+高斯消元