求一个C++ Problem 的解法

Question

小H觉得回文数字是非常美的，但是现实中遇到的数字串并非全部都是回文，因此小H要将连续若干个数变成回文，例如[2 4 6 4 3]，最少改变数字数量1个，即2改成3或3改成2。但是仅仅这么算作为第四题太简单了，因此要加大难度。出题人除了给你n个数ai外，还给了你一个奇数m。由经验可知n个数可以划分出n-m+1个子串（每个子串个数为m），现在需要你计算出每个子串都转换为回文的变化总次数。当然为了加深小H对题目的理解，出题者对样例进行如下解释，
例如样例中可以生成4个子串，其中第一个子串[2 3 9 3 6]需要变化1次，第二个子串[3 9 3 6 3]需要变化次数为1，第三个子串[9 3 6 3 9]需要变化次数为0，[3 6 3 9 7]需要变化次数为2。所以答案就是1+1+0+2=4。
输入
第一行输入n和m。
第二行输入n个整数ai。
输出
输出所有子串变成回文的变化次数之和
样例输入
8 5
2 3 9 3 6 3 9 7
样例输出
4
数据规模：
70%数据 n<=300
100%数据 1<=m<=n<=10^6 (m保证为奇数) 1<=ai<=10^6

Answer 1

这个问题可以使用动态规划的思想来解决。具体步骤如下：

遍历所有子串，计算每个子串变成回文的最少变化次数。
对于每个子串，分别从左右两侧开始，依次比较对应位置上的数字。如果不相等，则记录下需要变化的次数，同时把较小的数字赋值给较大的数字，使它们相等。
对于某些子串，当左右两侧同时到达中间位置时，可能存在一侧还有多余的数字没有处理。此时，我们可以直接把剩余的数字复制到另一侧，完成回文的变化。
计算每个子串变成回文的总共变化次数，并返回总共的变化次数。
下面是一种可能的C++代码实现：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    int ans = 0;
    for (int i = 0; i <= n - m; i++) {
        int left = i;
        int right = i + m - 1;
        int cnt = 0;
        while (left < right) {
            if (a[left] != a[right]) {
                cnt++;
                a[left] = a[right] = min(a[left], a[right]);
            }
            left++;
            right--;
        }
        ans += cnt;
    }

    cout << ans << endl;
    return 0;
}

代码中，我们使用vector来存储输入的数字序列，并通过两个指针left和right来遍历每个子串。在比较left和right位置上的数字时，如果它们不相等，则记录下需要变化的次数，并把较小的数字赋值给较大的数字，使它们相等。最后，把每个子串的变化次数加起来，得到总共的变化次数。

需要注意的是，当左右两侧同时到达中间位置时，可能存在一侧还有多余的数字没有处理。此时，我们可以直接把剩余的数字复制到另一侧，完成回文的变化。