CF607B Zuma

codeforces 原鏈接

題目描述

$\text{Genos}$ 最近在他的手機上下載了祖瑪游戲。在祖瑪游戲里，存在 $n$ 個一行的寶石，第 $i$ 個寶石的顏色是 $C_i$。這個游戲的目標是盡快的消滅一行中所有的寶石。

在一秒鐘，$\text{Genos}$ 能很快的挑選出這些有顏色的寶石中的一個回文的、連續的子串，并將這個子串移除。每當一個子串被刪除后，剩余的寶石將連接在一起，形成一個新的行列。

你的任務是：求出把整個寶石串都移除的最短時間。

輸入格式

第一行包含一個整數 $n(1\le n\le 500)$，表示寶石串的長度。第二行包含 $n$ 個被空格分開的整數，第 $i(1\le i\le n)$ 個表示這行中第 $i$ 個珠子的顏色。

輸出格式

輸出一個整數，把這行珠子移除的最短時間。

輸入輸出樣例 #1

輸入 #1

3
1 2 1

輸出 #1

1

輸入輸出樣例 #2

輸入 #2

3
1 2 3

輸出 #2

3

輸入輸出樣例 #3

輸入 #3

7
1 4 4 2 3 2 1

輸出 #3

2

說明/提示

在第一個例子中，$\text{Genos}$ 可以在一秒鐘就把這行珠子全部移走。在第二個例子中，$\text{Genos}$ 一次只能移走一個珠子，所以移走三個珠子花費他三秒。在第三個例子中，為了達到 $2$ 秒的最快時間，先移除回文串 $\text{4?4}$,再移除回文串 $\text{1?2?3?2?1}$。

感謝 @Administrator2004 提供的翻譯

solution

動態規劃。對于區間 [l, r]。如果首尾相同，則首尾可以最后一次消去，此時可轉換成 [l + 1, r - 1]。當然也可以不最后一次消去，則 [l, r] 必然可以分為兩個部分消去，[l, k] + [k + 1, r]

• 1 定義公式

  •  f[i][j]: 消去 [i, j] 最少的次數
    

• 2 遞推關系

  •  if a[i] == a[j]
    

  •      f[i][j] = min(f[i][j], f[i+1][j-1])
    

•  f[i][j] = min(f[i][j], f[i][k] + f[k+1][j])
  

• 3 結果

•  f[1][n]
  

• 4 初始值

  •  f[i][i] = 1
    

  •  f[i][i + 1] = 1 or 2 (相同就是1不同就是2)
    

代碼

include "algorithm"
#include "iostream"
#include "unordered_map"
#include "cstring"using namespace std;/** CF607B Zuma** 題目大意：* 有一個n(n<=500)的點的序列，每次可以消去一段連續的回文序列，問最少幾次可以將所有數都消去** 思路：動態規劃。對于區間 [l, r]。如果首尾相同，則首尾可以最后一次消去，此時可轉換成 [l + 1, r - 1]* 當然也可以不最后一次消去，則 [l, r] 必然可以分為兩個部分消去，[l, k] + [k + 1, r]* * 1 定義公式*      f[i][j]: 消去 [i, j] 最少的次數* 2 遞推關系*      if a[i] == a[j]*          f[i][j] = min(f[i][j], f[i+1][j-1])*      f[i][j] = min(f[i][j], f[i][k] + f[k+1][j])* 3 結果*      最大值 max(f[i][i + len - 1])*      取大值時 i 即為最開始去掉邊* 4 初始值*      f[i][i] = 1*      f[i][i + 1] = 1 or 2 (相同就是1不同就是2)*/const int INF = 0x7f7f7f7f;int f[505][505], n, a[505];int main() {cin >> n;for (int i = 1; i <= n; i++) cin >> a[i], f[i][i] = 1, f[i - 1][i] = (a[i] != a[i - 1]) + 1;for (int len = 3; len <= n; len++) {for (int i = 1, j; (j = i + len - 1) <= n; i++) {f[i][j] = 500;if (a[i] == a[j]) f[i][j] = f[i + 1][j - 1];for (int k = i; k < j; k++) f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j]);}}cout << f[1][n] << endl;return 0;
}

結果