【区间dp】 CF607B Zuma 题解

题面翻译

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

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

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

思路

考虑区间 dp。

记 $d{p}_{l,r}$ 为从 $l$ 消除到 $r$ 的最短时间，则：

$d{p}_{i,i}=1$

$\{\begin{array}{l}d{p}_{i,i+1}=1,c_i=c_{i+1}\\ d{p}_{i,i+1}=2,otherwise\end{array}$

对于 $r-l\ge 2$时，考虑转移，容易想到 $d{p}_{l,r}$ 可由 $d{p}_{l+1,r-1}$ 转移而来：

$\{\begin{array}{l}d{p}_{l,r}=d{p}_{l+1,r-1},c_l=c_r\\ d{p}_{l,r}=d{p}_{l+1,r-1}+1,otherwise\end{array}$

注意到 4 4 2 3 2 这个例子（样例 3），可以发现 $d{p}_{1,5}$ 可以由 $d{p}_{1,2}+d{p}_{3,5}$ 转移而来。综上所述：

$$d{p}_{l,r}=min(d{p}_{l,r},\underset{j=l}{\overset{r}{\min }}(d{p}_{l,j}+d{p}_{j+1,r}))$$

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,c[505],dp[505][505]; 
signed main() {scanf("%lld",&n);for(int i = 1;i <= n;i++) scanf("%lld",&c[i]),dp[i][i] = 1;for(int i = 1;i < n;i++) {if(c[i] == c[i + 1]) dp[i][i + 1] = 1;else dp[i][i + 1] = 2;}for(int i = 2;i <= n;i++) {for(int l = 1;l + i - 1 <= n;l++) {int r = l + i - 1;if(c[l] == c[r]) dp[l][r] = dp[l + 1][r - 1];else {dp[l][r] = min(dp[l + 1][r],dp[l][r - 1]) + 1;}for(int j = l;j <= r;j++) dp[l][r] = min(dp[l][r],dp[l][j] + dp[j + 1][r]);//printf("(%lld,%lld)%lld ",l,r,dp[l][r]);}//printf("\n");} printf("%lld\n",dp[1][n]);return 0;
}