「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
题解
状压，转移枚举子集
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
#include<iostream> #include<set> #include<map> #include<cstdio> #include<cstring> #include<cstdlib> #include<ctime> #include<vector> #include<queue> #include<algorithm> #include<cmath> #define inf 2000000000 #define pa pair<int,int> #define ll long long using namespace std; ll read() { ll 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*f; } int bin[20]; int t[20],w[20],f[65536],tim[65535],sum[65536]; int W,n; int main() { memset(f,127/3,sizeof(f)); bin[0]=1;for(int i=1;i<20;i++)bin[i]=bin[i-1]<<1; W=read();n=read(); for(int i=1;i<=n;i++) t[i]=read(),w[i]=read(); for(int i=1;i<bin[n];i++) for(int j=1;j<=n;j++) if(i&bin[j-1]) { tim[i]=max(tim[i],t[j]); sum[i]+=w[j]; } f[0]=0; for(int i=1;i<bin[n];i++) for(int j=i;j;j=i&(j-1)) if(sum[j]<=W)f[i]=min(f[i],tim[j]+f[i^j]); printf("%d",f[bin[n]-1]); return 0; } |
Subscribe
计数器 9854080
OI 课件=>
OI 课件=>