一道状压$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$