题目#

[IOI2000] 回文字串#

回文词是一种对称的字符串。任意给定一个字符串，通过插入若干字符，都可以变成回文词。此题的任务是，求出将给定字符串变成回文词所需要插入的最少字符数。

比如 $\verb!Ab3bd!$ 插入 $2$ 个字符后可以变成回文词 $\verb!dAb3bAd!$ 或 $\verb!Adb3bdA!$ ，但是插入少于 $2$ 个的字符无法变成回文词。

注意：此问题区分大小写。

记字符串长度为 $l$ 。

对于全部数据， $0<l\le 1000$ 。

题解#

设f[i][j]表示把f[i][j]变成回文的最少步数

然后分三种情况转移

代码#

1
#include<bits/stdc++.h>
2

3
using namespace std;
4
const int N = 1010;
5
char a[N];
6
int f[N][N];
7

8
int read()
9
{
10
  int f = 1, x = 0;
11
  char ch = getchar();
12
  while(ch < '0' || ch > '9')
13
  {
14
    if(ch == '-') f = -1;
15
    ch = getchar();
16
  }
17

18
  while(ch >= '0' && ch <= '9')
19
  {
20
    x = x * 10 + ch - '0';
21
    ch = getchar();
22
  }
23
  return f * x;
24
}
25

26
int main()
27
{
28
  scanf("%s", a + 1);
29

30
  int n = strlen(a + 1);
31
  for(int i = 1;i <= n;i++)
32
  {
33
    f[i][i] = 0;
34
  }
35

36
  for(int i = 1;i < n;i++)
37
  {
38
    if(a[i] == a[i + 1])
39
    {
40
      f[i][i + 1] = 0;
41
    }
42
    else
43
    {
44
      f[i][i + 1] = 1;
45
    }
46
  }
47

48
  for(int L = 3;L <= n;L++)
49
  {
50
    for(int i = 1;i + L - 1 <= n;i++)
51
    {
52
      int j = i + L - 1;
53
      f[i][j] = min(f[i][j - 1] + 1, f[i + 1][j] + 1);
54

55
      if(a[i] == a[j])
56
        f[i][j] = min(f[i + 1][j - 1], f[i][j]);
57
    }
58
  }
59
  cout << f[1][n];
60
  return 0;
61
}