bzoj2073 [POI2004]PRZ

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

Sample Output 42 HINT

Source

STAGE 2

状压dp 设dp[s]表示s状态我已经搬运完了 的最小时间是多少 首先预处理time&ww数组 然后枚举子集进行转移 注意转移的时候我有可能我自己这一次就是将他们全部搬运完的那一次因为我的枚举子集的方法无法枚举到0 所以我拎出来特判写一写的

但与此同时也需要判断下是否满足 重量的限制 然后直接dp即可

#include#include#include#define N 65536using 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(ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=gc();} while(ch<='9'&&ch>='0') x=x*10+ch-'0',ch=gc(); return x*f;}int bin[17],W,n,t[17],w[17],time[N],ww[N],dp[N];int main(){ freopen("bzoj2073.in","r",stdin); W=read();n=read();for (int i=0;i<=n;++i) bin[i]=1<W) continue; dp[s]=min(dp[s],dp[s1]+time[s2]); } }printf("%d\n",dp[bin[n]-1]); return 0;}

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