bzoj 2073 暴力

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).

Output

输出一个数表示最少的过桥时间.

Sample Input

100 3
24 60
10 40
18 50

Sample Output

HINT

Source

STAGE 2

这道题目的状态压缩暴力枚举转移的复杂度是∑(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-]);

 }

巴特西