【今日三题】爱丽丝的人偶(贪心) / 集合(排序) / 最长回文子序列(动态规划)

爱丽丝的人偶(贪心)

  • 爱丽丝的人偶

贪心策略：每次都选最高或最矮的，这样后面的可选择性就更大。

代码语言：javascript代码运行次数：0运行复制
#include <iostream>
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;
}

集合(排序)

  • 集合

方法一：归并排序中合并两个有序数组的操作，不过这里需要多加一个判断去重，当两个指针指向的值相等时，任意一个指针++，舍弃其中的一个值。

代码语言：javascript代码运行次数：0运行复制
#include <iostream>
#include <algorithm>
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有去重+排序的功能。

代码语言：javascript代码运行次数：0运行复制
#include <iostream>
#include <set>
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表只有右上部分有效。
代码语言：javascript代码运行次数：0运行复制
#include <iostream>
#include <string>
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;
}

本篇文章的分享就到这里了，如果您觉得在本文有所收获，还请留下您的三连支持哦~

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2025-04-15，如有侵权请联系 cloudcommunity@tencent 删除int动态规划集合排序指针