洛谷 B4336 分析（别看）

科技起源

2026-07-07 20:21:15

发布于：河北

1阅读

0回复

0点赞

原题链接

1 题目

1.1 题目所需求出内容

对于本题，最终要求：一个具体数值，代表最长长度

1.2 题目背景、允许、禁止与限制

背景：有一个长度为 $len$ 的字符串 $S$
允许：选择其中的一个子序列，使得这个子序列是回文字符串
禁止：
限制：最终要求求出符合要求子序列的最长长度

子序列的定义是：字符串 $A$ 再删除若干个不一定连续的字符后成为 $B$ ，就称字符串 $B$ 是字符串 $A$ 的子序列

1.3 题目数据范围与猜测

$3 \le len \le 1000 \longrightarrow O(n^2)$

1.4 一句话概括题意

有一个字符串，选择其中的一个子序列，使得这个子序列是回文字符串，求这个子序列长度最大能是多少

2 题目破题推导

注：以下七种方法都可以考虑一下

2.1 大拆小、小组大

2.2 正向思维转逆向思维，逆向思维转正向思维

2.3 以终为始、以始为终

2.4 数学

2.5 分情况考虑

既然这题已经有了一个关键信息“回文”
那么思考一下回文的条件：
如果 $S_i=S_j$ ，则区间 $[i+1,j-1]$ 中的最长回文子序列长度 $+ 2$ 就是到目前为止的最长回文子序列长度（注意因为这里是“子序列”所以无需考虑区间 $[i+1,j-1]$ 的回文情况）
否则只能是从区间 $[i+1,j]$ 和 $[i,j-1]$ 的较大值即可

2.6 手动推导

2.7 边界测试

3 模型匹配

先提取关键词：时刻求取当前最小值、区间
是 $\huge{区间动态规划}$

4 具体方案

4.1 动态规划定义（重点）

首先，先建立 dp 数组
设置 ${dp_i}_j$ 代表区间 $[i,j]$ 范围内最长回文子序列长度

4.2 初始化

求最小值，所以dp数组每一项都设为大值
但是一格一定是回文，因此对于每个 $i (1 \le i \le n)$ ，都要将 ${dp_i}_i$ 设置为 $1$

4.3 状态转移方程

我们的定义清晰了，合法方案也清晰了，因此直接就是（懒得打latex数学公式了）

for (int l = 2;l <= len;l++){
	for (int i = 1;i + l - 1 <= len;i++){
		int j = i + l - 1;
		if (s[i] == s[j]){
			dp[i][j] = dp[i + 1][j - 1] + 2;
		} else {
			dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
		}
	}
}

4.4 答案求取

${dp_1}_{len}$

5 最终代码（禁止抄袭，仅用于参考）

#include <bits/stdc++.h>
using namespace std;;

int len;
string s;
const int N = 1111;
int dp[N][N];

int main(){
	
	cin >> len >> s;
	s = ' ' + s;
	for (int i = 1;i <= len;i++){
		dp[i][i] = 1;
	}
	for (int l = 2;l <= len;l++){
		for (int i = 1;i + l - 1 <= len;i++){
			int j = i + l - 1;
			if (s[i] == s[j]){
				dp[i][j] = dp[i + 1][j - 1] + 2;
			} else {
				dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
			}
		}
	}
	cout << dp[1][len];
	
	return 0;
}