#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<vector> using namespace std; char a[1005], b[1005]; char at[1005], bt[1005]; int dp[1005][1005], l1, l2; void LCS(int i, int j) { for (i = 1; i <= l1; ++i) { for (j = 1; j <= l2; ++j) { if (a[i - 1] == b[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + 1; } else if (dp[i - 1][j] > dp[i][j - 1]) { dp[i][j] = dp[i - 1][j]; } else { dp[i][j] = dp[i][j - 1]; } } } } int cnt = 0; void fun() { int i = 0, j = 0, z = 0; char c[1005]; memset(c, 0, sizeof(c)); i = l1, j = l2; while (i != 0 && j != 0) { if (a[i - 1] == b[j - 1]) { c[z++] = a[--i]; j--; } else if (dp[i - 1][j] < dp[i][j - 1]) { j--; } else if (dp[i][j - 1] <= dp[i - 1][j]) { i--; } } printf("%d\n", z); if (z == 0) { printf("None\n"); } else { for (i = z - 1; i >= 0; i--) { printf("%c", c[i]); } printf("\n"); } } int main() { string at, bt; getline(cin, at); getline(cin, bt); int l1t = 0; int l2t = 0; for (int i = 0; i <= at.length(); ++i) { if (at[i] != ' ') { a[l1t++] = at[i]; } } for (int i = 0; i <= bt.length(); ++i) { if (at[i] != ' ') { b[l2t++] = bt[i]; } } memset(dp, 0, sizeof(dp)); l1 = strlen(a); l2 = strlen(b); LCS(l1, l2); fun(); return 0; } 中的else if (dp[i][j - 1] <= dp[i - 1][j]) { i--; }这段代码是当向上和向下相等的时候选择向上的值吗

不是的。这段代码的作用是在求解 LCS 的过程中，当 a[i-1] != b[j-1] 时，根据 dp 数组的值来决定下一步的选择方向。具体来说，如果 dp[i][j-1] > dp[i-1][j]，则说明 b[j-1] 不在 LCS 中，需要从 dp[i][j-1] 转移到 dp[i][j]；如果 dp[i][j-1] <= dp[i-1][j]，则说明 a[i-1] 不在 LCS 中，需要从 dp[i-1][j] 转移到 dp[i][j]。这里选择 dp[i-1][j] 是因为，当 dp[i-1][j] = dp[i][j-1] 时，选择 dp[i-1][j] 能够保证不会漏掉任何一种 LCS。

相关问题

#include <iostream> #include <fstream> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <climits> #include <string> #include <algorithm> #include <vector> #include <map> using namespace std; struct Value { char str[10000]; }; void structSort(Value *a, int n) { @你的代码 } int n; Value a[5000]; int main() { scanf("%d", &n); for (int i = 0; i<n; i++) { scanf("%s", a[i].str); } structSort(a, n); for (int i = 0; i<n; i++) { printf("%s\n", a[i].str); } return 0; }

这段代码给出了一个结构体数组 `a`，其中每个结构体包含一个字符串成员 `str`。接下来有一个函数 `structSort`，它需要你来实现。你需要使用任何一种排序算法对 `a` 数组进行排序，排序的依据是字符串的字典序（即按照字母顺序进行比较）。最后将排序后的字符串数组依次输出即可。

以下是可能的 `structSort` 实现方式之一，使用了标准库中的 `qsort` 函数：

int compare(const void *a, const void *b) {
    return strcmp(((Value *)a)->str, ((Value *)b)->str);
}

void structSort(Value *a, int n) {
    qsort(a, n, sizeof(Value), compare);
}

其中，`compare` 函数用于比较两个字符串的大小，将其作为参数传递给 `qsort` 函数进行排序。

#include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <cstring> #include <stack> #include <ctime> 怎么配置这些文件

这些文件是C++的头文件，不需要配置。在编写C++程序时，只需要在代码中包含这些头文件即可使用它们提供的函数和类。这些头文件一般都已经被安装在你的C++编译器中了，你只需要在代码中添加`#include`指令即可。比如，如果你想使用`iostream`头文件中的`cout`和`cin`，你可以这样写代码：

#include <iostream>
using namespace std;
int main(){
    cout<<"Hello World"<<endl;
    return 0;
}

如果你使用的是Visual Studio等IDE，一般会自动帮你添加这些头文件，你只需要专注于代码的编写即可。