750-D. New Year and Fireworks

2021-03-20 20:04:27 +0800 CST Tags: dp

出處：https://codeforces.com/contest/750/problem/D
提交：https://codeforces.com/contest/750/submission/110536865

問題：已知煙火在方格紙上的走訪規則如下，在同一層級底下會按照一個當前固定好的方向走完指定步數，接著要跳到下一個層級的時候就會爆炸成兩個分別與當前夾順時針與逆時針 45 度角的方向，接著繼續走完下一層的指定步數。給定 $n\in[1,30]$ 層各自指定的步數 $t_i$$\in[1,5]$，請問總共有幾個方格被煙火走訪過？

解法：很明顯地，整個地圖的大小至多不超過 300 乘以 300，直觀上可以直接模擬，有走過的方格就設為 true，模擬完畢後再一格一格統計。但有經驗的刷題仔應該可以立馬察覺，整個過程的時間複雜度至多為 $5+5\cdot2+5\cdot2^2+…+5\cdot2^{29}=5\cdot(2^{30}-1)\ge10^9$ 遠遠超過一般競程的負荷量，這個時候該怎麼辦呢？我就卡在這邊。我們知道 DP 不只可以拿地圖位置當索引值，也可以把執行狀態納入，而當初困擾我的點是不知道執行狀態會不會過多，但是經過精密的計算之後發現其實方向數 (8) 乘以最高總步數 (150) 最多也才 1200，再和 $300^2$ 相乘結果大約是 $10^8$，相較之下就比較有機會 AC，我們不能說完全綽綽有餘因為這個數量級其實還是沒有到很小。

實作：
有兩個地方我在扣頂的時候有稍微感到比較 tricky，一個是「方向」的概念，它除了指煙火停留/站在一個格子上的時候所面對的方位，也同時指按照此方向跨出去一步時的座標位移量，分清楚兩者的差異才不會怪怪；另外一個是記錄每一層所指定步數的陣列 layers，這邊我反而直接把它壓平，變成讓一層的 id (介於 1 到 n) 出現步數次，因為陣列全長也才 150，這樣的話只要發現下一個指定層 id 和當前指定層 id 不同，就知道要轉向了，實作上非常地方便。

 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


#include <bits/stdc++.h>
using namespace std;

vector<int> layers;
bool visit[300][300], state[300][300][8][150];

void dXdY(int dir, int &dX, int &dY) {
    dX = dY = 0;
    if (3<=dir && dir<=5) dX++;
    if ((0<=dir && dir<=1) || dir==7) dX--;
    if (1<=dir && dir<=3) dY++;
    if (5<=dir && dir<=7) dY--;
}

void DFS(int x, int y, int dir, int li) { // "li" stands for "layer index."
    if (li < layers.size()) {
        if (state[x][y][dir][li]) return;
        state[x][y][dir][li] = visit[x][y] = true;
        if (layers[li+1] > layers[li]) {
            int dX, dY, dir2;
            dir2=(dir+1)%8; dXdY(dir2, dX, dY); DFS(x+dX, y+dY, dir2, li+1);
            dir2=(dir+7)%8; dXdY(dir2, dX, dY); DFS(x+dX, y+dY, dir2, li+1);
        } else {
            int dX, dY; dXdY(dir, dX, dY);
            DFS(x+dX, y+dY, dir, li+1);
        }
    }
}

int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
    int n; cin >> n;
    for (int i=0; i<n; i++) {
        int d; cin >> d;
        while ((d--)>0) layers.push_back(i);
    }
    DFS(150, 150, 0, 0); int answer = 0;
    for (int i=0; i<300; i++)
        for (int j=0; j<300; j++)
            answer += visit[i][j];
    cout << answer;
    return 0;
}

結果： Example image