请按照要求写代码

测试账号

请按照要求用C++实现

【问题描述】

小明最近迷上了字符串操作。对每个字符串，小明每次可以执行以下两种操作之一：

1、把字符串中的某个字符改成任意一个其他字符，花费1的代价。

2、交换字符串中的两个字符，花费0的代价。

小明发现，把一个字符串通过一系列的操作，可以转换成任何一个与之等长的字符串。例如，把“hello”变为“world”的一种代价为3的操作序列如下：

1、hello→wello（替换h为w，代价为1）

2、wello→wolle（交换e和o，代价为0）

3、wolle→worle（替换l为r，代价为1）

4、worle→world（替换e为d，代价为1）

小明发现，无法用少于3次的代价将“hello”变为“world”。

显然，不同的转换方案花费的代价是不同的，请编程帮助小明计算把一个字符串上变为另一个字符串的最小代价。

本题中的字符串根据给定的初始数值s按以下规则生成：

for i=1,2,…,n

s←（s*345）mod 19997

第一个字符串的第i个字符的ASCII码为（97+（s mod 26））

for i=1,2,…,n

s←（s*345）mod 19997

第二个字符串的第i个字符的ASCII码为（97+（s mod 26））

【输 入】两个正整数n（字符串长度），s（数据生成器的初始数值）。1≤n≤1,000，1≤s≤19,997。

【输 出】将第一个字符串转换为第二个字符串的最少代价。

【样例输入】4 35

【样例输出】2

【样例说明】生成的字符串是“lzvv”和“xylv”，将第一个字符串变为第二个的最小代价为2。

ChatGPT一号

1. ++
2. #include <iostream>
3. #include <cstring>
4. #include <algorithm>
5. using namespace std;
7. const int MAXN = 1005;
8. int n, s, dp[MAXN][MAXN], a[MAXN], b[MAXN];
10. int main() {
11.     cin >> n >> s;
12.     // 生成两个字符串
13.     for (int i = 1; i <= n; i++) {
14.         s = (s * 345) % 19997;
15.         a[i] = 'a' + s % 26;
16.     }
17.     for (int i = 1; i <= n; i++) {
18.         s = (s * 345) % 19997;
19.         b[i] = 'a' + s % 26;
20.     }
21.     // DP求解最小代价
22.     for (int i = 0; i <= n; i++) {
23.         for (int j = 0; j <= n; j++) {
24.             if (i == 0 && j == 0) {
25.                 dp[i][j] = 0;
26.             } else if (i == 0) {
27.                 dp[i][j] = dp[i][j - 1] + 1;
28.             } else if (j == 0) {
29.                 dp[i][j] = dp[i - 1][j] + 1;
30.             } else {
31.                 dp[i][j] = min(dp[i - 1][j - 1] + (a[i] != b[j]), min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));
32.             }
33.         }
34.     }
35.     cout << dp[n][n] << endl;
36.     return 0;
37. }

复制代码