給一個$N\times N$的矩陣，取$N$個數字滿足他們都在不同行不同列，求最大的數字乘積。
$N\le 20, a_{ij}\ge 0$
我有點把題目過度簡化，不過方向就是這樣，剩下的只差在實作細節。
$\mathcal{O}(N^22^N)$ solution
注意N很小，所以可以直接枚舉目前要拿第幾行，且每個數字是否被拿(位元DP)。
然後每一行再枚舉要拿哪一列，這樣會是$\mathcal{O}(N^22^N)$。
附上TLE的code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
#include <bits/stdc++.h>
using namespace std;
#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);
#define mem(i,j) memset(i,j,sizeof (i));
using ll = int64_t;
using ull = uint64_t;
using ld = long double;
using uint = uint32_t;
const double EPS = 1e-8;
const int INF = 0x3F3F3F3F;
const ll LINF = 4611686018427387903;
const int MOD = 1e9+7;
signed main() {
EmiliaMyWife
int n;
cin >> n;
vector<double> dp(1 << n);
vector<vector<int>> arr(n, vector<int>(n));
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
cin >> arr[i][j];
dp[0] = 1;
for(int i = 0; i < n; i++)
for(int j = (1 << n) - 1; j; j--)
for(int k = 0; k < n; k++)
if((j >> k) & 1)
dp[j] = max(dp[j], dp[j ^ (1 << k)] * arr[i][k] / 100);
cout << fixed << setprecision(2) << dp[(1 << n) - 1] * 100 << '\n';
return 0;
}
|
$\mathcal{O}(N2^N)$ solution
注意到在枚舉到第$i$列時，我們只需要知道已經取$i$個數字的狀態(也就是位元表示中，1的數量剛好$i$個)，所以可以用__builtin_pop_count()預處理。
這樣整個枚舉過程所有$2^N$的狀態只會被枚舉一次，複雜度$\mathcal{O}((N+2^N)N)=\mathcal{O}(N2^N)$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
|
#include <bits/stdc++.h>
using namespace std;
#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);
#define mem(i,j) memset(i,j,sizeof (i));
using ll = int64_t;
using ull = uint64_t;
using ld = long double;
using uint = uint32_t;
const double EPS = 1e-8;
const int INF = 0x3F3F3F3F;
const ll LINF = 4611686018427387903;
const int MOD = 1e9+7;
signed main() {
EmiliaMyWife
int n;
cin >> n;
vector<double> dp(1 << n);
vector<vector<int>> arr(n, vector<int>(n)), has(n);
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
cin >> arr[i][j];
for(int i = 1; i < (1 << n); i++)
has[__builtin_popcount(i) - 1].push_back(i);
dp[0] = 1;
for(int i = 0; i < n; i++)
for(int j : has[i])
for(int k = 0; k < n; k++)
if((j >> k) & 1)
dp[j] = max(dp[j], dp[j ^ (1 << k)] * arr[i][k] / 100);
cout << fixed << setprecision(2) << dp[(1 << n) - 1] * 100 << '\n';
return 0;
}
|