查看原题请戳这里
题目大意：
从一个序列中每次取出一个回文串，剩余部分拼起来形成一个新的序列，问取几次能把这个序列取完。
这道题我们可以用区间DP的方法去解决。
若$a[1,n]$为题目给出的序列，用$f[i][j]$表示将区间$[i,j]$中的数取完需要的最少的次数，那么显然$f[i][i]=1$，且当$a[i]=a[j]$时$f[i][i+1]=1$，当$a[i] \neq a[i+1]$时$f[i][i+1]=2$。有用我们再后续进行动态规划时更新的最短的区间长度为$3$，所以$f[i][i]$和$f[i][i+1]$两种情况需要特殊处理。
在更新$f[i][j]$时，最简单的思路就是把$f[i][j]$分成$f[i][k]$和$f[k+1][j]$两部分进行处理（其中$k \in [i,j)$），即
$$f[i][j]=\min (f[i][j],f[i][k]+f[k+1][j]),k \in [i,j)$$
而对于$a[i]=a[j]$的情况，当区间$[i+1,j-1]$还剩最后一个可以一次取出的序列$b$时（显然$b$是回文的），我们可以将$a[i]$、$a[j]$和$b$组成一个新的回文串同时取出（即组成$a[i]\ b\ a[j]$），从而我们可知当$a[i]=a[j]$时，
$$f[i][j]=\min (f[i][j],f[i+1][j-1])$$
然后根据上述两式DP即可。
code:
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
28
29
30
31
32
33
34
35
36
37
38
| #include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define ll long long
#define INF 1000000009
#define qwq printf("qwq\n");
using namespace std;
int read() {
register int x = 0,f = 1;register char ch;
ch = getchar();
while(ch > '9' || ch < '0'){if(ch == '-') f = -f;ch = getchar();}
while(ch <= '9' && ch >= '0'){x = x * 10 + ch - 48;ch = getchar();}
return x * f;
}
int n,a[505],f[505][505];
int main() {
n = read();
for(int i = 1; i <= n; i++) a[i] = read();
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
f[i][j] = INF;
for(int i = 1; i <= n; i++) f[i][i] = 1, f[i][i + 1] = 1;
for(int i = 1; i < n; i++) if(a[i] != a[i + 1]) f[i][i + 1]++;
for(int i = 3; i <= n; i++)
for(int j = 1; j <= n - i + 1; j++) {
int l = j, r = j + i - 1;
if(a[l] == a[r]) f[l][r] = f[l + 1][r - 1];
for(int k = l; k < r; k++) f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r]);
}
printf("%d\n", f[1][n]);
return 0;
}
|
