‍ 关于作者会编程的土豆“不是因为看见希望才坚持而是坚持了才看见希望。”你好我是会编程的土豆一名热爱后端技术的Java学习者。正在更新中的专栏《数据结构与算法》《leetcode hot 100》《数据库mysql》作者简介后端学习者1.#includeiostream #includevector #includealgorithm using namespace std; int main() { string s; cin s; int n s.size(); vectorvectorintdp(n 1, vectorint(n 1)); string t s; reverse(s.begin(), s.end()); for (int i 1; i n; i) { for (int j 1; j n; j) { if (s[i - 1] t[j - 1]) { dp[i][j] dp[i - 1][j - 1] 1; } else { dp[i][j] max(dp[i - 1][j],dp[i][j - 1]); } } } cout n - dp[n][n] endl; return 0; }经典 LCS最长公共子序列所谓公共子序列就是可以不连续的两个字符串中相同的部分比如Ab3bd和db3bA公共子序列就是b3b那么这个题为什么要使用公共子序列呢诶很有意思这个题要求回文字串回文子串就是正反一样的那种他问要几个字母才能构成非常有意思咱们把原来的字符串反过来然后求这个字符串和原来的字符串的公共子序列这个公共子序列就是回文一样的咱们用总字符串大小减去这个大小就是答案2.#includeiostream #includevector #includealgorithm using namespace std; int main() { vectorintarr; int x; while (cin x) { arr.push_back(x); } reverse(arr.begin(), arr.end()); vectorinttail; for (int i 0; i arr.size(); i) { int x arr[i]; auto it upper_bound(tail.begin(), tail.end(), x); if (it tail.end()) { tail.push_back(x); } else { *it x; } } cout tail.size() endl; reverse(arr.begin(), arr.end()); vectorintg; for (int i 0; i arr.size(); i) { int x arr[i]; auto it lower_bound(g.begin(), g.end(), x); if (it g.end()) { g.push_back(x); } else *it x; } cout g.size() endl; return 0; }这个需要注意的是用while作为输入那么结束的时候就需要CtrlZ一下两个小问第一问要求求出最长的那个导弹长度题目要求递减咱们倒过来就是求递增因为算法只会求递增哈第二问求有几个递减序列咱们把原始数组递增的个数求出来就是有几个递减的3.#includeiostream #includevector #includealgorithm using namespace std; typedef struct node { int u, v, w; }node; vectorintparent; vectornodearr; vectorboolenemy; int find(int x) { if (parent[x] ! x) { parent[x] find(parent[x]); } return parent[x]; } bool f(node a, node b) { return a.w b.w; } int main() { int N, K; cin N K; enemy.resize(N 1, false); parent.resize(N 1); for (int i 1; i N; i) parent[i] i; for (int i 1; i K; i) { int mmm; cin mmm; enemy[mmm] true; } long long ssum 0; for (int i 1; i N - 1; i) { int u, v, w; cin u v w; ssum w; arr.push_back({ u,v,w }); } sort(arr.begin(), arr.end(), f); long long sum 0; for (int i 0; i arr.size(); i) { int u arr[i].u; int v arr[i].v; int w arr[i].w; int rootu find(u); int rootv find(v); if (!(enemy[rootu] enemy[rootv])) { if (rootu ! rootv) { parent[rootu] rootv; sum w; enemy[rootv] enemy[rootu] || enemy[rootv]; } } } cout ssum - sum endl; return 0; }