Zerojudge. c523 狗狗攻擊

Zerojudge. c523 狗狗攻擊

Problem

PDF

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

#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;
}