摘要
Title: 1222. 密码脱落
Tag: LCS、最长回文子串、区间dp
Memory Limit: 64 MB
Time Limit: 1000 ms

1222. 密码脱落

题意

X星球的考古学家发现了一批古代留下来的密码。
这些密码是由A、B、C、D 四种植物的种子串成的序列。
仔细分析发现，这些密码串当初应该是前后对称的（也就是我们说的镜像串）。
由于年代久远，其中许多种子脱落了，因而可能会失去镜像的特征。
你的任务是：
给定一个现在看到的密码串，计算一下从当初的状态，它要至少脱落多少个种子，才可能会变成现在的样子。
思路
- LCS
  求此串最少去掉几个成为回文串，也就是问此串的最长回文串
  将此串翻转，并求两者的最长公共子序列，便是最长回文串
- 区间dp

代码

LCS
ps: 加了求这个串是什么的函数

'''
Author: NEFU AB-IN
Date: 2022-04-03 10:00:26
FilePath: \ACM\Acwing\1222.py
LastEditTime: 2022-04-03 10:29:51
'''
N, M = 1100, 1100

dp = [[0] * M for _ in range(N)]
path = [[0] * M for _ in range(N)]

ans = ""


def LCS(i, j):
    global ans
    if i < 1 or j < 1:
        return
    if path[i][j] == 1:
        ans += a[i]
        LCS(i - 1, j - 1)
    elif path[i][j] == 2:
        LCS(i - 1, j)
    else:
        LCS(i, j - 1)


a = input()
b = " " + a[::-1]
a = " " + a
n, m = len(a) - 1, len(b) - 1

for i in range(1, n + 1):
    for j in range(1, m + 1):
        if a[i] == b[j]:
            dp[i][j] = dp[i - 1][j - 1] + 1
            path[i][j] = 1  #左上
        elif dp[i - 1][j] >= dp[i][j - 1]:
            dp[i][j] = dp[i - 1][j]
            path[i][j] = 2  #上
        else:
            dp[i][j] = dp[i][j - 1]
            path[i][j] = 3  #左

LCS(n, m)

print(ans)
print(n - dp[n][m])

区间dp

'''
Author: NEFU AB-IN
Date: 2022-04-03 10:55:42
FilePath: \ACM\Acwing\1222.1.py
LastEditTime: 2022-04-03 12:33:05
'''
N = int(1e3 + 10)
dp = [[0] * N for _ in range(N)]

s = " " + input()
n = len(s) - 1

for len in range(1, n + 1):
    i, j = 1, len
    while j <= n:
        if len == 1:
            dp[i][j] = 1
        else:
            dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
            if s[i] == s[j]:
                dp[i][j] = max(dp[i][j], dp[i + 1][j - 1] + 2)
        i += 1
        j += 1

print(n - dp[1][n])

1222. 密码脱落

题意

思路

代码