Zerojudge. c523 狗狗攻擊

Zerojudge. c523 狗狗攻擊

Problem

Solution

這題其實有兩種做法,分別為DP+線段樹與貪心法,比賽當初給的正解好像是DP的解法,不過我自己寫的時候是用貪心法解決的。
以下敘述中,$x,y$分別代表正反面最後一次的攻擊招式,$c$為當前攻擊招式。
從最直覺的地方出發,我們知道如果$A>B$,則一定會希望某面遭到同樣招式的連續攻擊;若$A<B$,則希望變換攻擊招數。所以我們分成兩種情況討論,分別是$A>B$和$A<B$。

$A>B$

假設第一次攻擊打在正面,那第一次要換面打的時候,就是x!=c。因為$A>B$,所以我們可以確定x==c時打在正面一定會比打在反面有更佳解。而以下討論的均為正反面均受過至少一次攻擊的情況:
如果$x$跟$y$其中有一個為$c$,則一定是把當前攻擊加到上次也是受到招式$c$的那面,所以傷害會加上A。但是如果$x,y$均不等於$c$的話,就比較複雜了。這時我們就要考慮,到底是什麼原因,才會使得目前的攻擊加在正/反面會影響到最大傷害?
舉個例子:

根據上面推論出來的法則,首先我會把1打在正面,2打在反面,接著3就不知道要打在哪裡了$(x=1, y=2, c=3)$。但是我們知道,唯一能使傷害最大化的方法,就是盡量讓之後的招式1打到正面,或是招式2打到反面,而且這中間不能穿插其他種類的招式。雖然要同時達成是不可能的,不過可以選擇比較好的方法,也就是看之後1和2誰比較早出現,就把當前招式打在另一邊。以剛剛的例子為例,第三次攻擊時不知道要打在哪裡,這時候就比較第四次以後1,2誰比較早出現,而因為1在第5次時就出現了,所以我們就把當前攻擊加在反面上。

$A<B$

在$A<B$的情況中,其實想法跟$A>B$的一樣,只是把這裡的「相等」看成$A<B$時的「不相等」,「不相等」看成「相等」就可以了,而推論的方法則跟上述一樣。

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <bits/stdc++.h>
using namespace std;

int n, a, b, Front, Back, mx;
int in[200001];
deque<int> pos[200001];
long long ans1, ans2;

int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> a >> b;
for (int i = 1; i <= n; i++) {
int j;
cin >> j;
in[i] = j;
pos[j].emplace_back(i);
mx = max(mx, j);
}
bool mode = a > b;
pos[Front = in[1]].pop_front();
for (int i = 1; i <= mx; i++)
pos[i].emplace_back(100000000);
pos[0].emplace_back(100000001);
for (int i = 2; i <= n; i++) {
int &cur = in[i];
pos[cur].pop_front();
if (mode) {
if (cur == Front || cur == Back)
ans1 += a;
else {
if (Back) {
if (pos[Front][0] > pos[Back][0])
Front = cur;
else
Back = cur;
ans1 += b;
}else
Back = cur;
}
}else {
if (cur == Front && cur == Back)
ans1 += a;
else if (cur == Front || cur == Back) {
if (Back)
ans1 += b;
Front = Back = cur;
}else {
if (pos[Front][0] > pos[Back][0])
Back = cur;
else
Front = cur;
ans1 += b;
}
}
}
for (int i = 2; i <= n; i++)
if (in[i] == in[i - 1])
ans2 += a;
else
ans2 += b;
cout << max(ans1, ans2) << '\n';
return 0;
}