P3147 USACO16OPEN 262144 P 題解

發表於 分類於 閱讀次數： Waline： 文章字數： 1.1k

DP 系列。

題面

看題，Luogu

合併相鄰的相同數字，變成數字加一。求獲得的最大值。

思考

最初想到的是基礎的區間 DP，不做解釋：

1
2
3
4
5
6
7
8
9
10
11
12
13
long long ans = 0;
for(int len = 2; len<=N; len++){
    for(int i = 1; i+len-1<=N; i++){
        int y = i+len-1;
        for(int k = i; k<y; k++){
            if(DP[i][k] == DP[k+1][y]){
                DP[i][y] = max(DP[i][y], DP[i][k] + 1);
            }
        }
        ans = max(ans, DP[i][y]);
    }
}
cout << ans << endl;

但是 $ 2 n $ ，顯然會 MLE。

最佳化

借鑑思路，我們發現可以使用類似倍增的方法去做。

用狀態 f[i][j] 表示 合成之後結果為 i，右端點為 j 的區間的左端點位置，如果 值為 0 即 不可行。

因為題目要找兩個相鄰相等的區間，合成。有：

1
2
3
f[i][j] = f[i-1][f[i-1][j]];

把 f[i][j] 拆分成兩個能合成為 i-1 的區間

即

1
2
3
4
5
                 f[i-1][j]
    |------<i-1>-----|----<i-1>-----|
    j                      f[i-1][f[i-1][j]] 

如果 f[i-1][j] 或 f[i-1][f[i-1][j]] 不成立，f[i][j] 就不成立，即轉移為 0

那如何表示結果？

記錄 ans，如果 f[i][j] 可行，就更新 ans。因為 i 遞增，所以不需要 max 操作。

得到

1
2
3
4
5
6
7
8
9
10
for(int i =2; i<=58; i++){
    for(int j = 1; j<=N; j++){
        if(!DP[i][j]){
            DP[i][j] = DP[i-1][DP[i-1][j]];
        }
        if(DP[i][j]){
            ans = i;
        }
    }
}

注意我們倍增合併，所以 log2262144 + 40 = 58 是可能獲得的最大值。

初始化

顯然不合並是可行的，所以在輸入的時候，初始化

1
2
3
4
5
for(int i = 1; i<=N; i++){
    int in;
    cin >> in;
    DP[in][i] = i+1;
}

關於 i+1：為了避免區間重複，我們 f[i][j] 表示的區間是左閉右開區間，所以右端點是 i+1

小結

這道題是區間 DP 狀態最佳化，DP 學習之路漫漫，還需要多加練習。