Zuma

题面翻译

$texttt{Genos}$ 最近在他的手机上下载了祖玛游戏。在祖玛游戏里，存在 $n$ 个一行的宝石，第 $i$ 个宝石的颜色是 $C_i$。这个游戏的目标是尽快的消灭一行中所有的宝石。

在一秒钟，$texttt{Genos}$ 能很快的挑选出这些有颜色的宝石中的一个回文的、连续的子串，并将这个子串移除。每当一个子串被删除后，剩余的宝石将连接在一起，形成一个新的行列。

你的任务是：求出把整个宝石串都移除的最短时间。

输入格式

第一行包含一个整数 $n(1 \leq n \leq 500)$，表示宝石串的长度。第二行包含 $n$ 个被空格分开的整数，第 $i(1 le i le n)$ 个表示这行中第 $i$ 个珠子的颜色。

输出格式

输出一个整数，把这行珠子移除的最短时间。

样例说明

在第一个例子中，$texttt{Genos}$ 可以在一秒钟就把这行珠子全部移走。在第二个例子中，$texttt{Genos}$ 一次只能移走一个珠子，所以移走三个珠子花费他三秒。在第三个例子中，为了达到 $2$ 秒的最快时间，先移除回文串 $texttt{4 4}$,再移除回文串 $texttt{1 2 3 2 1}$。

样例 #1

样例输入 #1

1
2
3
1 2 1

样例输出 #1

1
1

样例 #2

样例输入 #2

1
2
3
1 2 3

样例输出 #2

1
3

样例 #3

样例输入 #3

1
2
7
1 4 4 2 3 2 1

样例输出 #3

1
2

解题思路

这个题目主要就是通过计算删除掉哪些子回文串，可以让我们得最终的字符串变成回文串，首先需要判断我们首尾是否相同，相同的话就有可能是最终的回文串的首尾，也可能不是，所以即使相同也需要做后面的不相同的操作。如果首尾不相同，我们就需要知道我们这个字符串是如何被删除得来的回文串，首先我们收尾不相同，我们删除的回文串一定是在最右边或者最左边，所以我们其实就可以遍历我们所有的区间，将整个区间划分为不同的子区间来考虑，因为我们用dp，我们只需要划分两个区间就好了。这两个子区间在前面会递归划分为各种子区间。

解题代码

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
public class Main {
    public static int N = 510;
    public static int[][] dp = new int[N][N];
    public static int[] a = new int[N];
    public static Scanner sc = new Scanner(System.in);
    public static void main(String[] args) throws  Exception{
        int n = sc.nextInt();
        for(int i = 1;i <= n;i++){
            Arrays.fill(dp[i],0x3f3f3f3f);
            a[i] = sc.nextInt();
            dp[1][i] = dp[0][i] = 1;
        }
 
 
        for(int len = 2;len <= n;len++){
            for(int i = 1;i + len - 1 <= n;i++){
                int j = i + len - 1;
                for(int k = 1;k < len;k++){
                    dp[len][i] = Math.min(dp[k][i] + dp[len - k][i + k],dp[len][i]);
                }
                if(a[i] == a[j]) dp[len][i] = Math.min(dp[len][i],dp[len-2][i+1]);
            }
        }
 
        System.out.println(dp[n][1]);
    }
}