首页 > 代码库 > BZOJ2073 [POI2004]PRZ

BZOJ2073 [POI2004]PRZ

2024-11-23 20:15:02   203人阅读

自从知道"poi~"是什么意思以后。。。稳如poi~

一眼状压动规：

f[s]表示到集合s的时候，最少的时间

再定义time[s]表示集合s里的人一次通过桥的总时间，time[s] = max(t[i]) (i ∈ s)

sum[s]表示集合s里的人的总重量， sum[s] = Σ w[i] (i ∈ s)

f[s] = min(f[s1] + time[s2]) (sum[s2] ≤ W 且 s1 ∪ s2 = s, s1 ∩ s2 = ∅)

 

技术分享
 1 /************************************************************** 2     Problem: 2073 3     User: rausen 4     Language: C++ 5     Result: Accepted 6     Time:340 ms 7     Memory:1572 kb 8 ****************************************************************/ 9  10 #include <cstdio>11 #include <cstring>12 #include <algorithm>13  14 using namespace std;15 const int N = 25;16 const int M = 65536;17  18 int n, W;19 int bin[N];20 int t[N], w[N];21 int f[M], time[M], sum_w[M];22  23 int main() {24   int i, j;25   scanf("%d%d", &W, &n);26   for (i = bin[0] = 1; i < 20; ++i)27     bin[i] = bin[i - 1] << 1;28   for (i = 1; i <= n; ++i)29     scanf("%d%d", t + i, w + i);30   for (i = 1; i < bin[n]; ++i)31     for (j = 1; j <= n; ++j)32       if (i & bin[j - 1])33     time[i] = max(time[i], t[j]), sum_w[i] += w[j];34   memset(f, 127 / 3, sizeof(f));35   f[0] = 0;36   for (i = 1; i < bin[n]; ++i)37     for (j = i; j; j = i & (j - 1))38       if (sum_w[j] <= W)39     f[i] = min(f[i], time[j] + f[i ^ j]);40   printf("%d\n", f[bin[n] - 1]);41   return 0;42 }
View Code

 

BZOJ2073 [POI2004]PRZ


联系
我们