2073: [POI2004]PRZ
Time Limit: 10 Sec Memory Limit: 64 MB
Submit: 442 Solved: 327
[Submit][Status][Discuss]
Description
一只队伍在爬山时碰到了雪崩,他们在逃跑时遇到了一座桥,他们要尽快的过桥. 桥已经很旧了, 所以它不能承受太重的东西. 任何时候队伍在桥上的人都不能超过一定的限制. 所以这只队伍过桥时只能分批过,当一组全部过去时,下一组才能接着过.
队伍里每个人过桥都需要特定的时间,当一批队员过桥时时间应该算走得最慢的那一个,每个人也有特定的重量,我们想知道如何分批过桥能使总时间最少.
队伍里每个人过桥都需要特定的时间,当一批队员过桥时时间应该算走得最慢的那一个,每个人也有特定的重量,我们想知道如何分批过桥能使总时间最少.
Input
第一行两个数: w – 桥能承受的最大重量(100 <=
w <= 400) 和 n – 队员总数(1 <= n <= 16). 接下来n 行每行两个数分别表示: t –
该队员过桥所需时间(1 <= t <= 50) 和 w – 该队员的重量(10 <= 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
HINT
Source
这道题目的状态压缩暴力枚举转移的复杂度是∑(Cn,i * 2^i)渐进与3^n
这个我不知道，考试是打表找复杂度吧。
#pragma GCC optimize(2)
#pragma G++ optimize(2)
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring> #define N 70007
#define inf 1000000007
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-;ch=getchar();}
while(isdigit(ch)){x=(x<<)+(x<<)+ch-'';ch=getchar();}
return x*f;
} int w,n;
int weight[N],tim[N],f[N];
struct Node
{
int t,w;
}a[]; void dfs(int dep,int now,int slow,int zl)
{
if(dep==n)
{
weight[now]=zl;
tim[now]=slow;
return;
}
dep++;
dfs(dep,now<<|,max(slow,a[dep].t),zl+a[dep].w);
dfs(dep,now<<,slow,zl);
}
int main()
{
w=read(),n=read();
for (int i=;i<=n;i++)a[i].t=read(),a[i].w=read();
dfs(,,,);
f[]=;int up=<<n;
for (int i=;i<up;i++)f[i]=inf;
for (int i=;i<up;i++)
{
for (int j=i;j;j=(j-)&i)
if(weight[j]<=w) f[i]=min(f[i],f[i^j]+tim[j]);
}
printf("%d\n",f[up-]);
}