题目链接
https://open.kattis.com/problems/names
题意
给出一个字符串
有两种操作
0.在字符串的最末尾加一个字符
1.更改字符串中的一个字符
求最少的操作步数使得字符串变成回文串
思路
由于回文串具有对称关系
所以给出一串回文串 最多的操作步数 就是 len / 2
只改一半不同的字符就可以了
所以我们可以先将字符串倒置
然后依次一步一步 挪过去 与原串比较 比出有多少个不同的字符
那么操作次数就是 挪位数+不同字符个数/ 2
比如说
样例
kaia
aiak 挪位数 0 不同字符个数 4 总操作数 2
kaia
aiak 挪位数 1 不同字符个数 0 总操作数1
就是答案了
AC代码
#include <cstdio>
#include <cstring>
#include <ctype.h>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <map>
#include <stack>
#include <set>
#include <list>
#include <numeric>
#include <sstream>
#include <iomanip>
#include <limits>
#define CLR(a, b) memset(a, (b), sizeof(a))
#define pb push_back
#define bug puts("***bug***");
//#define gets gets_s
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <string, int> psi;
typedef pair <string, string> pss;
typedef pair <double, int> pdi;
const double PI = acos(-1.0);
const double E = exp(1.0);
const double eps = 1e-8;
const int INF = 0x3f3f3f3f;
const int maxn = 1e4 + 10;
const int MOD = 1e9 + 7;
int main()
{
string s;
getline(cin, s);
string tmp = s;
reverse(s.begin(), s.end());
int len = s.size();
int ans = len / 2;
for (int i = 0; i < len; i++)
{
int step = i;
int dif = 0;
for (int j = i, k = 0; j < len; j++, k++)
{
if (tmp[j] != s[k])
dif++;
}
dif /= 2;
ans = min(ans, dif + step);
}
cout << ans << endl;
}