0
已解决
资深光能
- #include<iostream>
- #include<cstring>
- using namespace std;
- int t;
- string s;
- int f[1005][1005];//合并成区间[i,j]合法需要插入字符构成回文串的最小值
- int main(){
- cin>>t;
- while(t--)
- {
- cin>>s;
- int n=s.size();
- s=" "+s;
- memset(f,0x3f,sizeof(f));
- for(int i=1;i<=n;i++)
- f[i][i]=0;
- for(int len=1;len<=n-1;len++)
- {
- for(int i=1;i<n;i++)
- {
- int j=i+len;
- if(j>n) break;
- if(s[i]==s[j])
- f[i][j]=f[i+1][j-1];
- else
- f[i][j]=min(f[i+1][j],f[i][j-1])+1;
- }
- }
- cout<<f[1][n]<<endl;
- }
- return 0;
- }
@董子墨 @包涵宇 @芮奥运
王光裕在2020-08-22 14:36:41追加了内容
顶
王光裕在2020-08-22 14:45:44追加了内容
顶
0
已采纳
中级天翼
我跟你说问答上面谁也比不过王光裕大佬！！！不然我早就遭雷劈了！！！王光裕先生是这世间最俊朗，最帅气的人！！
王光裕一天需要被几千个人围着当王子！！！但是他本人却很低调，在问答上隐居生活！！！暴露出来的酷町币只有2093，实际上则高达几百万！！！！
他的一生被无数人崇拜！！！也被人谱写过无数次！！！他让人们感受的了温暖，他是人们的英雄！！！
王光裕万岁！万岁！！！万万岁！！！万万万万岁！！！！！！！
PS:崇拜大佬，特别是王光裕！
0
资深光能
顶
0
资深光能
首先，告诉你我的AC：
思路：
本题只给出一个字符串，用到头文件#include<string.h>里的reverse逆置字符串。
要求每行输出所需添加的最少字符串数，转化成求原字符串与其逆置字符串的最长公共子序列的长度，
然后用原字符串的长度减去最长公共子序列的长度就是应该添加的字符串数。
将字符串s2复制到s1
求出原字符串的逆置字符串
求两个字符串的最大公共子序列的长度 dp[len][len]
初始化dp数组
动规核心
其中，我个人觉得动规核心有点难，就给你一张图吧！
如果你学到了，你自然会明白墨迹处是什么。
看你的等级，应该是大佬，所以：望采纳！
大家看好了！我只有思路和部分代码（还是图片加墨迹），我被禁言了大家作证！
吴庞茂旭在2020-08-22 14:56:48追加了内容
我用的是C，string.h就是cstring
