题目链接：
注意到“您可以按任意顺序执行以下两种运算零次或多次”。
因此，解决这个问题的一个重要观察点是，你可以假设 \(A\) 操作执行了几次，然后 \(B\) 操作执行了几次。你也可以假设 \(A\) 操作最多被执行 \(N\) 次(因为执行 \(N\) 次就会使它处于原始状态)
有了这个观察结果，你就会意识到，小约束条件允许我们检查所有可能的 $A $ 操作次数。执行 \(B\) 操作所需的最小次数就是应该匹配但目前不匹配的字符对数。
时间复杂度为 \(O(n^2)\)。
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const int N = 5010;
i64 ans;
int main()
{
ios::sync_with_stdio(false), cin.tie(nullptr);
int n, A, B;
string s;
cin >> n >> A >> B >> s;
i64 ans = 1e18;
for (int i = 0; i < n; i++) {
i64 res = 1LL * A * i;//1LL可以将后面的临时数据扩容成long long
for (int j = 0; j < n / 2; j++) {
res += (s[j] != s[n - 1 - j]) * B;//在固定A操作的次数下考虑B操作需要执行多少次。
}
ans = min(ans, res);
rotate(s.begin(), s.begin()+1, s.end());//左旋转
}
cout << ans;
return 0;
}
另一种不使用 \(\rm std::rotate\) 的思路是，把字符串 \(s\) 复制一份连接上去，每次截取一个从 \(S_i\) 开始，长度为 \(n\) 的子串，就相当于进行了 \(i\) 次操作 \(A\)，然后再看这个子串是否回文进行操作 \(B\)，与之前思路一致。
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const int N = 5010;
i64 ans;
int main()
{
ios::sync_with_stdio(false), cin.tie(nullptr);
int n, A, B;
string s;
cin >> n >> A >> B >> s;
s = s + s;
i64 ans = 1e18;
for (int i = 0; i < n; i++) {
int l = i, r = i + n - 1;
i64 res = 1LL * A * i;
while (l < r) {
res += (s[l] != s[r]) * B;
l++, r--;
}
ans = min(ans, res);
}
cout << ans;
return 0;
}
注：std::rotate 的函数原型为
template <class ForwardIterator> void rotate (ForwardIterator first, ForwardIterator middle, ForwardIterator last);
具体而言。\(\sf std::rotate\) 交换范围 \(\rm [first,last)\) 中的元素，方式满足元素 \(\rm middle\) 成为新范围内的首个元素，而 \(\rm middle-1\) 成为最后元素。
此函数的前提条件是 \(\rm [first,middle)\) 和 \(\rm [middle,last)\) 为合法范围。
示例程序：
#include <bits/stdc++.h>
int main()
{
std::vector<int> v;
for (int i = 1; i <= 9; i++) v.push_back(i);//1 2 3 4 5 6 7 8 9
std::rotate(v.begin(), v.begin()+3, v.end());
for (auto i : v) std::cout << i << " ";//4 5 6 7 8 9 1 2 3
return 0;
}
旋转过程可以按下图来理解：
