动态规划--最长上升子序列模型(二)

简介: AcWing算法提高课内容,本文讲解 动态规划

四、AcWing 482. 合唱队形

1.题目

本题链接:合唱队形

本博客提供本题截图:

image.png

2.逻辑解释

看成一个上升子序列 + 一个下降子序列,f[i]表示以i为结尾的最长上升子序列,g[i]表示以i为开头的最长下降自序列,本题问最少需要几名同学出列,其实就是问出列后队伍最长是多长,即我们需要求一个上升子序列和一个下降子序列,使得这两个子序列的长度和最长,即求max(f[i] + g[i] - 1),-1的原因是因为i这个位置算了两次,然后就变成了一个简单的 LIS问题.


3.AC代码

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;
int f[N], g[N];
int h[N];
int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> h[i];
    for (int i = 1; i <= n; i ++ ) 
    {
        f[i] = 1;
        for (int j = 1; j < i; j ++ ) 
            if (h[j] < h[i])
                f[i] = max(f[i], f[j] + 1);
    }
    for (int i = n; i; i -- )
    {
        g[i] = 1;
        for (int j = n; j > i; j -- )
            if (h[j] < h[i])
                g[i] = max(g[i], g[j] + 1);
    }
    int res = 0;
    for (int i = 1; i <= n; i ++ )
        res = max(res, f[i] + g[i] - 1);
    cout << n - res << endl;
    return 0;
}


五、AcWing 1012. 友好城市

1.题目

本题链接:友好城市

本博客提供本题截图:

4.png

2.逻辑解释

本题就是造桥,每个桥有两个参数x1和x2,表示桥的一头连接在上岸坐标为x1的地方,一头连在下岸坐标为x2的地方,我们所求的为在要求桥不想交的前提下,建尽可能多的桥

image.png

以上图一中红色的就是题目中的样例,图二中蓝色的则是我们最后选择的桥梁。

我们可以按照上岸的坐标从小到大来枚举,然后我们只需关心下岸的坐标之间有何关系即可;于是,不难发现,上坐标从小到大枚举选择到的桥,其对应下坐标也必然是从小到大的.

3.AC代码

#include <iostream>
#include <algorithm>
#include <map>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 5010;
PII h[N];
int f[N];
int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i ++ ) cin >> h[i].x >> h[i].y;
    sort(h, h + n);
    int res = 0;
    for (int i = 0; i < n; i ++ )
    {
        f[i] = 1;
        for (int j = 0; j < n; j ++ ) 
            if (h[j].y < h[i].y)
                f[i] = max(f[i], f[j] + 1);
        res = max(res, f[i]);
    }
    cout << res << endl;
    return 0;
}


目录
相关文章
|
2天前
|
弹性计算 人工智能 安全
云上十五年——「弹性计算十五周年」系列客户故事(第二期)
阿里云弹性计算十五年深耕,以第九代ECS g9i实例引领算力革新。携手海尔三翼鸟、小鹏汽车、微帧科技等企业,实现性能跃升与成本优化,赋能AI、物联网、智能驾驶等前沿场景,共绘云端增长新图景。
|
8天前
|
存储 弹性计算 人工智能
【2025云栖精华内容】 打造持续领先,全球覆盖的澎湃算力底座——通用计算产品发布与行业实践专场回顾
2025年9月24日,阿里云弹性计算团队多位产品、技术专家及服务器团队技术专家共同在【2025云栖大会】现场带来了《通用计算产品发布与行业实践》的专场论坛,本论坛聚焦弹性计算多款通用算力产品发布。同时,ECS云服务器安全能力、资源售卖模式、计算AI助手等用户体验关键环节也宣布升级,让用云更简单、更智能。海尔三翼鸟云服务负责人刘建锋先生作为特邀嘉宾,莅临现场分享了关于阿里云ECS g9i推动AIoT平台的场景落地实践。
【2025云栖精华内容】 打造持续领先,全球覆盖的澎湃算力底座——通用计算产品发布与行业实践专场回顾
|
7天前
|
人工智能 自然语言处理 自动驾驶
关于举办首届全国大学生“启真问智”人工智能模型&智能体大赛决赛的通知
关于举办首届全国大学生“启真问智”人工智能模型&智能体大赛决赛的通知
|
7天前
|
云安全 人工智能 自然语言处理
阿里云x硅基流动:AI安全护栏助力构建可信模型生态
阿里云AI安全护栏:大模型的“智能过滤系统”。
|
8天前
|
编解码 自然语言处理 文字识别
Qwen3-VL再添丁!4B/8B Dense模型开源,更轻量,仍强大
凌晨,Qwen3-VL系列再添新成员——Dense架构的Qwen3-VL-8B、Qwen3-VL-4B 模型,本地部署友好,并完整保留了Qwen3-VL的全部表现,评测指标表现优秀。
624 7
Qwen3-VL再添丁!4B/8B Dense模型开源,更轻量,仍强大
|
10天前
|
存储 机器学习/深度学习 人工智能
大模型微调技术:LoRA原理与实践
本文深入解析大语言模型微调中的关键技术——低秩自适应(LoRA)。通过分析全参数微调的计算瓶颈,详细阐述LoRA的数学原理、实现机制和优势特点。文章包含完整的PyTorch实现代码、性能对比实验以及实际应用场景,为开发者提供高效微调大模型的实践指南。
750 2