1-1-月赛T2 分析（别看）

科技起源

2026-07-08 14:39:00

发布于：河北

0阅读

0回复

0点赞

1 题目

1.1 题目所需求出内容

对于本题，最终要求：一个最小值

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

背景：有一个长度为 $n$ 的字符串 $s$ ，其中有 $k$ 种字符，每种字符都有相对应的添加或删除花费
允许：在字符串的任意位置添加或删除一个元素，最终使得整字符串成为回文串
禁止：

1.3 数据范围与猜测

限制：最终求最小花费
$1 \le n \le 2000 \longrightarrow O(n^2)$

1.4 一句话概括题意

有一个字符串，其中每种字符都有独特的删除和添加的花费，求将整个字符串变为回文串的最小花费

2 题目破题推导

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

2.1 大拆小、小组大

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

2.3 分情况考虑

一个长度为 $n$ 的回文串 $s$ 满足：对于所有 $k(1 \le k \le \lceil{n\div2}\rceil)$ ， $s_k=s_{n-k+1}$
因此，对于一个区间 $[i,j]$ 来说，如果 $s[i]=s[j]$ 那么如果区间 $[i+1,j-1]$ 是回文串，则整体是回文串，否则不是
如果对于一个区间 $[i,j]$ 来说，如果 $s[i] \neq s[j]$ ，则为了使它变成回文，有四种可能的选择

删掉左边的字符 $s_i$ ，现在需要的是把区间 $[i+1,j]$ 变为回文的最小花费
删掉右边的字符 $s_j$ ，现在需要的是把区间 $[i,j-1]$ 变为回文的最小花费
在左边增加一个字符 $s_j$ ，现在需要的是把区间 $[i,j-1]$ 变为回文的最小花费
在右边增加一个字符 $s_i$ ，现在需要的是把区间 $[i+1,j]$ 变为回文的最小花费

2.4 数学

2.5 以终为始、以始为终

2.6 手动推导

2.7 边界测试

3 模型匹配

格式为："关键词：...... $\longrightarrow$ $\huge{......}$ "

关键词：区间，回文 $\longrightarrow$ $\huge{区间动态规划}$

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

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

int k, n;
string s;
const int N = 26, M = 2222;
int dp[M][M];
int a[N], d[N];

int main(){
	
	cin >> k >> n;
	cin >> s;
	s = " " + s;
	for (int i = 1;i <= k;i++){
		char c;
		cin >> c;
		int idx = c - 'a';
		cin >> a[idx] >> d[idx]; 
	}
	memset(dp, 0x3f, sizeof(dp));
	for (int i = 1;i <= n;i++){
		dp[i][i] = 0;
	}
	for (int len = 2;len <= n;len++){
		for (int l = 1;l + len - 1 <= n;l++){
			int r = l + len - 1;
			if (s[l] == s[r]){
				if (len == 2){
					dp[l][r] = 0;
				} else {
					dp[l][r] = min(dp[l][r], dp[l + 1][r - 1]);
				}
			} else {
				dp[l][r] = min({dp[l][r], dp[l + 1][r] + a[s[l] - 'a'], dp[l][r - 1] + a[s[r] - 'a'], dp[l + 1][r] + d[s[l] - 'a'], dp[l][r - 1] + d[s[r] - 'a']});
			}
		}
	}
	cout << dp[1][n]; 
	
	return 0;
}