#include<iostream> #include<cstring> #include<cstdio> using namespace std; int max(int a, int b){ return a > b?a:b; } char s1[5001], s2[5001]; int n; int len = 0; int f[2][5001]; int maxx = 0; int main(){ while(scanf("%d", &n)!=EOF){ memset(s1, 0, sizeof(s1)); memset(s2, 0, sizeof(s2)); maxx = 0; scanf("%s", s1); int k = 0; for(int i = n-1; i >= 0; i--){ s2[n-1-i] = s1[i]; } memset(f, 0, sizeof(f)); for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ if(s1[i-1] == s2[j-1]) f[i%2][j] = f[(i-1)%2][j-1]+1; else f[i%2][j] = max(f[(i-1)%2][j],f[i%2][j-1]); } } cout << n-f[n%2][n] <<endl; } }代码解释
时间: 2024-01-28 10:02:57 浏览: 26
这段代码实现了一个求解回文串最小插入次数的问题。下面是代码的解释:
1. 首先定义了一个 `max` 函数,用于求两个数的最大值。
```c++
int max(int a, int b){
return a > b?a:b;
}
```
2. 然后定义了一些变量和数组:
```c++
char s1[5001], s2[5001]; // 两个字符串
int n; // 字符串长度
int len = 0; // 最长回文子序列的长度
int f[2][5001]; // 动态规划数组
int maxx = 0; // 记录最长回文子序列的长度
```
3. 接下来是主函数:
```c++
int main(){
while(scanf("%d", &n)!=EOF){ // 多组数据
memset(s1, 0, sizeof(s1)); // 初始化数组
memset(s2, 0, sizeof(s2));
maxx = 0;
scanf("%s", s1); // 读入字符串
int k = 0;
for(int i = n-1; i >= 0; i--){ // 将字符串反转
s2[n-1-i] = s1[i];
}
memset(f, 0, sizeof(f)); // 初始化动态规划数组
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
if(s1[i-1] == s2[j-1]) // 如果两个字符相等
f[i%2][j] = f[(i-1)%2][j-1]+1; // 最长回文子序列长度加一
else
f[i%2][j] = max(f[(i-1)%2][j],f[i%2][j-1]); // 否则取左边和上面的最大值
}
}
cout << n-f[n%2][n] <<endl; // 输出最小插入次数
}
}
```
4. 对于每个输入的字符串,首先将其反转,然后用动态规划求解最长回文子序列的长度,最终输出字符串长度减去最长回文子序列的长度即为最小插入次数,使其变成回文串。
5. 总体思路比较清晰,需要注意的是,这里用到了滚动数组技巧,将二维数组压缩成一维数组,可以减小空间复杂度。