有三個人(P, E, C)走在路上很無聊，於是他們開始了一個遊戲。
他們將要走的路是一條筆直的路徑，依序有$N\le 2\times 10^6$顆石塊排成一排。這$N$顆石塊很特別，每一顆都只能被P、E、C其中一個人撿起。之後P、E、C會在走過這條路時選一個區間開始撿石塊，將區間內所有可以被他撿起的石塊都拿起來。然而為了避免P、E、C三個人在路途中打架，他們所選定的區間兩兩交集必須要是空的。
說石持那十塊，P、E、C三個人已經走完這條路並且撿好石塊了。請計算他們三人所持有的石塊個數總和最大是多少。
可以發現如果路上有任何地方沒被三個人的區間涵蓋到，那把這個地方也給涵蓋一定不會比較差，所以問題就變成把整條路切成三段，每段分配給其中一人。
考慮$dp[N][X][{S}]$，代表第$N$個石頭是分配給$X$，且已經$S$內的人皆已經被分配過了。
轉移時，可能前一顆石頭也是給$X$，或者是給$S$內除了$X$的人。
而這題會卡記憶體，所以要滾動，設$X$為人數(在這題中為3)，時間複雜度$\mathcal{O}(NX^22^X)$，空間複雜度$\mathcal{O}(2^XX)$。
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
50
51
52
53
54
55
56
57
58
59
|
#include <bits/stdc++.h>
using namespace std;
#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);
int dp[2][1 << 3][3];
signed main() {
EmiliaMyWife
int n;
cin >> n;
string s;
cin >> s;
int a = 0, b = 1;
for(int i = 1; i <= n; i++) {
swap(a, b);
char c = s[i - 1];
int owo;
if(c == 'P')
owo = 0;
if(c == 'C')
owo = 1;
if(c == 'E')
owo = 2;
for(int j = 0; j < (1 << 3); j++) {
for(int k = 0; k < 3; k++) {
if(!(j >> k & 1))
continue;
dp[a][j][k] = dp[b][j][k];
for(int w = 0; w < 3; w++) {
if(j >> w & 1)
dp[a][j][k] = max(dp[a][j][k], dp[b][j ^ (1 << k)][w]);
}
if(k == owo)
dp[a][j][k]++;
}
}
}
int ans = 0;
for(int i = 0; i < (1 << 3); i++)
for(int j = 0; j < 3; j++)
ans = max(ans, dp[a][i][j]);
cout << ans << '\n';
return 0;
}
|