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

结果