【今日三题】爱丽丝的人偶(贪心) / 集合(排序) / 最长回文子序列(动态规划)
⭐️个人主页：@小羊 ⭐️所属专栏：每日两三题 很荣幸您能阅读我的文章，诚请评论指点，欢迎欢迎 ~
目录
爱丽丝的人偶(贪心)
- 爱丽丝的人偶
贪心策略：每次都选最高或最矮的，这样后面的可选择性就更大。
#include using namespace std;int main(){ int n; cin >> n; int l = 1, r = n; while (l <= r) { cout << l++ << \" \"; if (l <= r) cout << r-- << \" \"; } return 0;}集合(排序)
- 集合
方法一：归并排序中合并两个有序数组的操作，不过这里需要多加一个判断去重，当两个指针指向的值相等时，任意一个指针++，舍弃其中的一个值。
#include #include using namespace std;const int N = 10001;int a[N], b[N];int main() { int n, m; cin >> n >> m; for (int i = 0; i < n; i++) cin >> a[i]; for (int i = 0; i < m; i++) cin >> b[i]; sort(a, a + n); sort(b, b + m); int l = 0, r = 0; while (l < n && r < m) { if (a[l] < b[r]) cout << a[l++] << \" \"; else if (a[l] == b[r]) l++; else cout << b[r++] << \" \"; } while (l < n) cout << a[l++] << \" \"; while (r < m) cout << b[r++] << \" \"; return 0;}方法二：利用set的特性，set有去重+排序的功能。
#include #include using namespace std;int main() { int n, m; cin >> n >> m; set<int> s; for (int i = 0; i < n + m; i++) { int x; cin >> x; s.insert(x); } for (auto e : s) cout << e << \" \"; return 0;}最长回文子序列(动态规划)
- 最长回文子序列
- dp[i][j]：区间[i, j]内最长回文子序列的长度；
- 填表顺序：从下往上，从左往右；
- dp表只有右上部分有效。
#include #include using namespace std;int dp[1001][1001];int main(){ string s; cin >> s; int n = s.size(); for (int i = n - 1; i >= 0; i--) { dp[i][i] = 1; for (int j = i + 1; j < n; j++) { if (s[i] == s[j]) dp[i][j] = dp[i + 1][j - 1] + 2; else dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]); } } cout << dp[0][n - 1] << endl; return 0;}本篇文章的分享就到这里了，如果您觉得在本文有所收获，还请留下您的三连支持哦~
