P4329 [COCI2006-2007#1] Bond

${\color{Cyan}{>>Question}}$

一道状压$dp$的好题

首先拿到题,想都没想就设$f[l][i][j]$表示第$l$个人在状态$i$(此处的状态为任务是否被完成)下选j任务的最大成功率

有$$f[l][i][j] = max\left \{ f[l-1][i-\left \{ j \right \}][k]*p[l][j] \right \}$$

时间复杂度$O(n^3*2^n)$

空间复杂度$O(n^2*2^n)$

显然都不行

但我还是压了一维空间后交了一下,竟然有$75pts$

代码如下

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cstdio>
 4 #include <cstring>
 5 #define ll long long
 6 using namespace std;
 7 
 8 template <typename T> void in(T &x) {
 9     x = 0; T f = 1; char ch = getchar();
10     while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
11     while( isdigit(ch)) {x = 10 * x + ch - 48; ch = getchar();}
12     x *= f;
13 }
14 
15 template <typename T> void out(T x) {
16     if(x < 0) x = -x , putchar('-');
17     if(x > 9) out(x/10);
18     putchar(x%10 + 48);
19 }
20 //-------------------------------------------------------
21 
22 const int N = 20;
23 
24 int n;
25 double f[1<<N][N];
26 double p[N][N];
27 
28 int main() {
29     //freopen("0_1.in","r",stdin);
30     int i,j,k,l,a;
31     in(n);
32     for(i = 0;i < n; ++i) {
33         for(j = 0;j < n; ++j) {
34             in(a); p[i][j] = a/100.0;
35         }
36     } 
37     for(j = 0;j < n; ++j) f[1<<j][j] = p[0][j];//第一层//debug p[0][j] -> p[1][j]
38     for(l = 1;l < n; ++l) {
39         for(i = (1<<n)-1; i >= 0; --i) {//逆序 
40             for(j = 0;j < n; ++j) {
41                 if(!(i&(1<<j))) continue;
42                 for(k = 0;k < n; ++k) {
43                     if(k == j || !(i&(1<<k))) continue;
44                     f[i][j] = max(f[i][j],f[i^(1<<j)][k]*p[l][j]);
45                 }
46             }
47         }
48     }
49     double ans = 0;
50     for(i = 0;i < n; ++i) ans = max(ans,f[(1<<n)-1][i]);
51     printf("%lf",ans*100.0);
52     return 0;
53 }

再想想发现第三维根本不需要放进状态中

令$f[l][i]$表示前$l$个人状态为$i$的最大成功率,只需枚举当前选$j$号任务

有$$f[l][i] = max\left \{ f[l-1][i-\left \{ j \right \}]*p[l][j] \right \}$$

时间复杂度$O(n^2*2^n)$

空间复杂度$O(n*2^n)$

时间还是不行,但我压了空间交了一遍,有$90pts$

代码如下

 

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cstdio>
 4 #include <cstring>
 5 #define ll long long
 6 using namespace std; 
 7 
 8 template <typename T> void in(T &x) {
 9     x = 0; T f = 1; char ch = getchar();
10     while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
11     while( isdigit(ch)) {x = 10 * x + ch - 48; ch = getchar();}
12     x *= f;
13 }
14 
15 template <typename T> void out(T x) {
16     if(x < 0) x = -x , putchar('-');
17     if(x > 9) out(x/10);
18     putchar(x%10 + 48);
19 }
20 //-------------------------------------------------------
21 
22 const int N = 20;
23 
24 int n;
25 double f[1<<N];
26 double p[N][N];
27 
28 int main() {
29     int i,j,l;
30     in(n);
31     for(i = 0;i < n; ++i) {
32         for(j = 0;j < n; ++j) {
33             in(p[i][j]); p[i][j] /=100.0;
34         }
35     } 
36     for(j = 0;j < n; ++j) f[1<<j] = p[0][j];//第一层
37     for(l = 1;l < n; ++l) {
38         for(i = (1<<n)-1; i >= 0; --i) {//逆序 
39             for(j = 0;j < n; ++j) {
40                 if(!(i&(1<<j))) continue;
41                     f[i] = max(f[i],f[i^(1<<j)]*p[l][j]);
42             }
43         }
44     }
45     printf("%lf",f[(1<<n)-1]*100.0);
46     return 0;
47 }

 

最后再仔细思考,我们之所以要枚举第$l$个人是因为我们要知道当前以及选了几个人(才有$p$数组)

但实际上状态$i$中$1$的个数就是当前以及选了几个人

所以我们令$f[i]$表示状态$i$下的最大成功率

有$$f[i] = max\left \{ f[i-\left \{ j \right \}]*p[cnt][j] \right \}$$

$cnt$为$i$中$1$的个数

 

时间复杂度$O(n*2^n)$

空间复杂度$O(n*2^n)$

可行

代码如下

 

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cstdio>
 4 #include <cstring>
 5 #define ll long long
 6 using namespace std; 
 7 
 8 template <typename T> void in(T &x) {
 9     x = 0; T f = 1; char ch = getchar();
10     while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
11     while( isdigit(ch)) {x = 10 * x + ch - 48; ch = getchar();}
12     x *= f;
13 }
14 
15 template <typename T> void out(T x) {
16     if(x < 0) x = -x , putchar('-');
17     if(x > 9) out(x/10);
18     putchar(x%10 + 48);
19 }
20 //-------------------------------------------------------
21 
22 const int N = 21;
23 
24 int n;
25 double f[1<<N];
26 double p[N][N];
27 
28 int main() {
29     int i,j;
30     in(n);
31     for(i = 0;i < n; ++i) {
32         for(j = 0;j < n; ++j) {
33             in(p[i][j]); p[i][j] /=100.0;
34         }
35     }
36     f[0] = 1;
37     for(i = 1;i < (1<<n); ++i) {
38         int s = i,cnt = -1;//注意这里是0基准 
39         /*while(s) {
40             if(s&1) ++cnt;
41             s >>= 1; 
42         }*/
43         for(;s;s >>= 1) if(s&1) ++cnt;//统计1的个数
44         for(j = 0;j < n; ++j) {
45             if(i&(1<<j)) f[i] = max(f[i],f[i^(1<<j)]*p[cnt][j]);
46         }
47     }
48     printf("%lf",f[(1<<n)-1]*100.0);
49     return 0;
50 }

 

但这题还可以用二分图带权匹配或费用流$A$了

好吧我也不会$QwQ$

 

上一篇:教你炒股票21:缠中说禅买卖点分析的完备性


下一篇:yolov3中生成网络输入数据格式的voc_lable.py文件代码解读(笔记)