AcWing 1.2.1 最长上升子序列模型 + 动态规划 + 图解（详细）

（1）acwing 4557. 最长上升子序列 4557. 最长上升子序列 - AcWing题库

给定一个长度为 N 的整数序列 a1,a2,…,aN。请你计算该序列的最长上升子序列的长度。上升子序列是指数值严格单调递增的子序列

输入格式
  • 第一行包含整数 N
  • 第二行包含 N个整数 a1,a2,…,aN
输出格式
  • 一行，一个整数，表示最长上升子序列的长度
数据范围
  • 1≤N≤1000
  • 0≤ai≤100000
输入样例：
7
1 7 3 5 9 4 8
输出样例：
4

 C++代码：

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1010;

int n,res=0;
int arr[N],dp[N];

int main() {
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&arr[i]);
    for(int i=1;i<=n;i++) {
        dp[i]=1;
        for(int j=1;j<i;j++) {
            if(arr[j]<arr[i]) 
                dp[i] = max(dp[i],dp[j]+1);
        }
        if (res < dp[i]) res = dp[i]; // 取长的子序列
    }
    printf("%d\n",res);
    return 0;
}

也可以这样写：

int main() {
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&arr[i]);
    dp[0]=1;
    for(int i=1;i<n;i++) {
        dp[i]=1;
        for(int j=0;j<i;j++) {
            if(arr[j]<arr[i]) 
                dp[i] = max(dp[i],dp[j]+1);
        }
        if (res < dp[i]) res = dp[i]; // 取长的子序列
    }
    printf("%d\n",res);
    return 0;
}

======================================================

int main() {
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&arr[i]);
    dp[1]=1;
    for(int i=2;i<=n;i++) {
        dp[i]=1;
        for(int j=1;j<i;j++) {
            if(arr[j]<arr[i]) 
                dp[i] = max(dp[i],dp[j]+1);
        }
        if (res < dp[i]) res = dp[i]; // 取长的子序列
    }
    printf("%d\n",res);
    return 0;
}

（2）acwing1017-怪盗基德的滑翔翼

假设城市中一共有 N幢 建筑排成一条线，每幢建筑的高度各不相同。初始时，怪盗基德可以在任何一幢建筑的顶端。他可以选择一个方向逃跑，但是不能中途改变方向（因为中森警部会在后面追击）。因为滑翔翼动力装置受损，他只能往下滑行（即：只能从较高的建筑滑翔到较低的建筑）。他希望尽可能多地经过不同建筑的顶部，这样可以减缓下降时的冲击力，减少受伤的可能性。请问，他最多可以经过多少幢不同建筑的顶部(包含初始时的建筑)？

输入格式

  • 输入数据第一行是一个整数K，代表有K组测试数据
  • 每组测试数据包含两行：第一行是一个整数N，代表有N幢建筑。第二行包含N个不同的整数，每一个对应一幢建筑的高度h，按照建筑的排列顺序给出

输出格式

  • 对于每一组测试数据，输出一行，包含一个整数，代表怪盗基德最多可以经过的建筑数量

数据范围

  • 1≤K≤100,
  • 1≤N≤100,
  • 0<h<10000

输入样例：

3
8
300 207 155 299 298 170 158 65
8
65 158 170 298 299 155 207 300
10
2 1 3 4 5 6 7 8 9 10

输出样例：

6
6
9

思路：移动方向一旦确定，就转换成了LIS问题，那么可以看作是两个方向的最长上升子序列问题，答案res为正向和逆向LIS两个过程中的较大者。

 C++代码：

// 当确定完方向和起点后，最长的距离是什么呢？
// 起点：a[i]
// 最长距离：以a[i]为结尾的最长上升子序列

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

int n;
int arr[N],dp[N];

int main() {
	int T;
	scanf_s("%d", &T);
	while (T--) {
		scanf_s("%d", &n);
		for (int i = 1; i <= n; i++) scanf_s("%d", &arr[i]);
		// 正向求解LIS问题
		int res = 0;
		for (int i = 1; i <= n; i++) {
			dp[i] = 1;
			for (int j = 1; j < i; j++) {
				if (arr[i] > arr[j]) dp[i] = max(dp[i], dp[j] + 1);
			}
			res = max(res, dp[i]);
		}
		// 反向求解LIS问题
		for (int i = n; i>=1; i--) {
			dp[i] = 1;
			for (int j = n; j > i; j--) {
				if (arr[i] > arr[j]) dp[i] = max(dp[i], dp[j] + 1);
			}
			res = max(res, dp[i]);
		}
		printf("%d\n", res);
	}
	return 0;
}

（3）acwing1014-登山问题

五一到了，ACM队 组织大家去登山观光，队员们发现山上一共有N个景点，并且决定按照顺序来浏览这些景点，即每次所浏览景点的编号都要大于前一个浏览景点的编号。同时队员们还有另一个登山习惯，就是不连续浏览海拔相同的两个景点，并且一旦开始下山，就不再向上走了。队员们希望在满足上面条件的同时，尽可能多的浏览景点，你能帮他们找出最多可能浏览的景点数么？

输入格式

  • 第一行包含整数N，表示景点数量
  • 第二行包含N个整数，表示每个景点的海拔

输出格式

  • 输出一个整数，表示最多能浏览的景点数

数据范围

  • 2≤N≤1000

输入样例

8
186 186 150 200 160 130 197 220

输出样例

4

本题实质上是求正向和反向两次LIS问题，两次的LIS过程相互独立，故所求为两端LIS过程中最长上升子序列的最大长度之和

  • res = max(res,f[i]+g[i]-1)

C++代码：

/*
	条件1：按照编号递增的顺序来浏览 => 必须是子序列
	条件2：相邻两个景点不能相同
	条件3：一旦开始下降，就不能上升了

	目标：求最多能浏览多少景点
*/

#include <iostream>
#include <algorithm>

using namespace std;
const int N = 1010;

int n;
int arr[N];
int f[N], g[N];

int main() {
	scanf_s("%d", &n);
	for (int i = 1; i <= n; i++) scanf_s("%d", &arr[i]);
	for (int i = 1; i <= n; i++) {
		f[i] = 1;
		for (int j = 1; j < i; j++) {
			if (arr[i] > arr[j]) f[i] = max(f[i], f[j] + 1);
		}
	}
	for (int i = n; i >= 1; i--) {
		g[i] = 1;
		for (int j = n; j > i; j--) {
			if (arr[i] > arr[j]) 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);
	printf("%d\n", res);
	return 0;
}

（4）acwing 482.合唱队形 482. 合唱队形 - AcWing题库

N 位同学站成一排，音乐老师要请其中的 (N−K) 位同学出列，使得剩下的 K 位同学排成合唱队形。合唱队形是指这样的一种队形：设 K 位同学从左到右依次编号为 1，2…，K 他们的身高分别为 T1，T2，…，TK 则他们的身高满足 T1<…<Ti>Ti+1>…>TK(1≤i≤K)。你的任务是，已知所有 N 位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。

输入格式
  • 输入的第一行是一个整数 N ，表示同学的总数
  • 第二行有 N 个整数，用空格分隔，第 i  个整数 Ti  是第 i 位同学的身高(厘米)
输出格式
  • 输出包括一行，这一行只包含一个整数，就是最少需要几位同学出列
数据范围
  • 2≤N≤100
  • 130≤T≤230

思路： 如果要使得出列的同学数量最少的话，就意味着要使剩下的数量最多。那意思就是要找到一个先上升再下降的序列，选个最大的。然后再用总数减去这个长度。

#include <iostream>
#include <algorithm>

using namespace std;
const int N = 1010;

int n;
int arr[N];
int f[N],g[N];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &arr[i]);
    for(int i=1;i<=n;i++) {
        f[i] = 1;
        for(int j=1;j<i;j++) {
            if(arr[i]>arr[j]) f[i] = max(f[i], f[j] + 1);
        }
    }
    for(int i=n;i>=1;i--) {
        g[i] = 1;
        for(int j=n;j>i;j--) {
            if(arr[i]>arr[j]) 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);
    printf("%d",n-res);
    return 0;
}

（5）acwing 1012.友好城市

输入样例： 

7
22 4
2 6
10 3
15 12
9 8
17 17
4 2

输出样例： 

4

 

>>思路和分析

对于任意一种合法的建立桥梁的方式，都可以对应一种因变量的上升子序列。反之，对于因变量的任何一个上升子序列，我们都可以唯一的对应一个合法的建桥方式。每一种建桥方式，建桥的数量和上升子序列的长度是相同的。因此左边集合（所有合法的建桥方式）的长度最大值就等于右边集合（上升子序列）的长度的最大值。
解法：先按照自变量的大小，把因变量排序。排好之后得到一个序列，然后在序列当中求最长的一个上升子序列。
排序思路：看一下什么会出现相交的情况？
本质：如果选出来的桥梁是没有交叉的，那么就意味着按照其中某一个点来排序，那么另外一个点对应的位置也一定要使有序的才可以。因为一旦出现逆序，就是有交叉的。没有交叉也就意味着一定没有逆序的。那本题其实就可以转化为求最长上升子序列的长度。 

C++代码： 

#include <iostream>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

const int N = 5010;

int n;
PII q[N];
int f[N];

int main() {
	scanf_s("%d", &n);
	for (int i = 0; i < n; i++) scanf_s("%d%d", &q[i].first, &q[i].second);
	sort(q, q + n);

	int res = 0;
	for (int i = 0; i < n; i++) {
		f[i] = 1;
		for (int j = 0; j < i; j++) {
			if (q[i].second > q[j].second) f[i] = max(f[i], f[j] + 1);
		}
		res = max(res, f[i]);
	}
	printf("%d\n",res);
	return 0;
}

（6）acwing 1016.最长上升子序列和

输入样例：  

7
1 7 3 5 9 4 8

 输出样例： 

18

 C++代码：

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;
int n;
int a[N], f[N];

int main() {
	scanf_s("%d", &n);
	for (int i = 1; i <= n; i++) scanf_s("%d", &a[i]);
	for (int i = 1; i <= n; i++) {
		f[i] = a[i];
		for (int j = 1; j <i; j++) {
			if (a[i] > a[j]) f[i] = max(f[i], f[j] + a[i]);
		}
	}
	int res = 0;
	for (int i = 1; i <= n; i++) res = max(res, f[i]);
	printf("%d\n", res);
	return 0;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/106606.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

TEMU电器等产品要求提供CE-LVD,不接受CE-EMC

TEMU电器等产品要求提供CE-LVD,不接受CE-EMC

最近&#xff0c;TEMU平台对CE资质要求越来越严格&#xff0c;针对CE资质又提出了两点新要求。首先&#xff0c;TEMU平台要求提供正式的CE证书&#xff0c;且必须有签发实验室的盖章或者签字。这一要求是为了确保产品符合欧洲市场的安全标准&#xff0c;也是为了保护消费者的利…
阅读更多...
Tomcat的动静分离

Tomcat的动静分离

一、动态负载均衡 3、台虚拟机模拟&#xff1a; 代理服务器&#xff1a;51 tomcat动态页面&#xff1a;53,54 关闭防火墙和安全机制 配置代理服务器&#xff0c;由于做的是七层代理&#xff0c;所以要在http模块配置 配置前端页面 <!DOCTYPE html> <html> <…
阅读更多...
解决node项目一个极度困难的捕获异常却无法读取异常信息的问题

解决node项目一个极度困难的捕获异常却无法读取异常信息的问题

这个项目是集成了第三方NeteaseCloudMusicApi项目的接口代码&#xff0c;我没有直接使用它的接口&#xff0c;因为需要再跑一个npm run开个端口&#xff0c;感觉很麻烦。 所以下定决心&#xff0c;使用拆分代码的方式&#xff0c;硬生生将这个api项目的部分api接口代码集成到了…
阅读更多...
构造类型详解及热门题型结构体大小的计算

构造类型详解及热门题型结构体大小的计算

在编写程序时&#xff0c;简单的变量类型已经不能满足程序中各种复杂数据的需求&#xff0c;因此c语言还提供了构造类型的数据&#xff0c;构造数据是有基本数据按照一定的规则组成的。 目录 结构体类型的概念 结构体变量的定义 结构体变量的初始化 结构体变量的引用 结构…
阅读更多...
软件工程——期末复习知识点汇总

软件工程——期末复习知识点汇总

本帖的资料来源于某国内顶流高校的期末考试资料&#xff0c;仅包含核心的简答题&#xff0c;大家结合个人情况&#xff0c;按需复习~ 总的来说&#xff0c;大层面重点包括如下几个方面&#xff1a; 软件过程需求工程 设计工程软件测试软件项目管理软件过程管理 1.掌握软件生命…
阅读更多...
flutter 使用FlutterJsonBeanFactory工具遇到的问题

flutter 使用FlutterJsonBeanFactory工具遇到的问题

如下图&#xff0c;使用FlutterJsonBeanFactory工具生成的数据类 但是其中 生成的 import package:null/&#xff0c;导致的错误&#xff1a;Target of URI doesn’t exist: ‘package:null/generated/json/asd.g.dart’ 尝试过的方法&#xff1a; 手动添加包名&#xff0c;…
阅读更多...
Map集合 遍历：lambda方式

Map集合 遍历：lambda方式

package day01;import java.util.*;public class Mapday1 {public static void main(String[] args) {/* HashMap 无序 不重复&#xff0c;会覆盖前面 无索引*/System.out.println("--------------------");Map<String, Integer> map new HashMap<>();m…
阅读更多...
Kafka - 消息队列的两种模式

Kafka - 消息队列的两种模式

文章目录 消息队列的两种模式点对点模式&#xff08;Point-to-Point&#xff0c;P2P&#xff09;发布/订阅模式&#xff08;Publish/Subscribe&#xff0c;Pub/Sub&#xff09; 小结 消息队列的两种模式 消息队列确实可以根据消息传递的模式分为 点对点模式发布/订阅模式 这两…
阅读更多...
Android笔记（八）：基于CameraX库结合Compose和传统视图组件PreviewView实现照相机画面预览和照相功能

Android笔记（八）：基于CameraX库结合Compose和传统视图组件PreviewView实现照相机画面预览和照相功能

CameraX是JetPack库之一&#xff0c;通过CameraX可以向应用增加相机的功能。在下列内容中&#xff0c;将介绍一个结合CameraX实现一个简单的拍照应用。本应用必须采用Android SDK 34。并通过该简单示例&#xff0c;了解传统View层次组件的UI组件如何与Compose组件结合实现移动应…
阅读更多...
【代码思路】2023mathorcup 大数据数学建模B题 电商零售商家需求预测及库存优化问题

【代码思路】2023mathorcup 大数据数学建模B题 电商零售商家需求预测及库存优化问题

各位同学们好&#xff0c;我们之前已经发布了第一问的思路视频&#xff0c;然后我们现在会详细的进行代码和结果的一个讲解&#xff0c;然后同时我们之后还会录制其他小问更详细的思路以及代码的手把手教学。 大家我们先看一下代码这一部分&#xff0c;我们采用的软件是Jupyte…
阅读更多...
tftp服务的搭建

tftp服务的搭建

TFTP服务的搭建 1 先更新一下apt包 sudo apt-get update2 服务器端(虚拟机上)安装 TFTP相关软件 sudo apt-get install xinetd tftp tftpd -y3 创建TFTP共享目录 mkdir tftp_sharetftp_shaer的路径是/home/cwz/tftp_share 3.1 修改共享目录的权限 sudo chmod -R 777 tftp…
阅读更多...
python操作MySQL、SQL注入问题、视图、触发器、事务、存储过程、函数、流程控制、索引(重点)

python操作MySQL、SQL注入问题、视图、触发器、事务、存储过程、函数、流程控制、索引(重点)

python操作MySQL(重要) SQL的由来&#xff1a; MySQL本身就是一款C/S架构&#xff0c;有服务端、有客户端&#xff0c;自身带了有客户端&#xff1a;mysql.exe python这门语言成为了MySQL的客户端(对于一个服务端来说&#xff0c;客户端可以有很多) 操作步骤&#xff1a; …
阅读更多...
是谁在造谣杭州取消直播带货？

是谁在造谣杭州取消直播带货？

我是卢松松&#xff0c;点点上面的头像&#xff0c;欢迎关注我哦&#xff01; 这个世道&#xff0c;谣言的传播成本很低&#xff1a;比如“杭州禁止直播带货”这件事。 就在今天若水跟我说&#xff1a;“杭州禁止直播是谣言了&#xff0c;辟谣了”让我也赶紧隐藏或删除内容&…
阅读更多...
【触想智能】工控一体机与5G物联网技术结合是未来发展趋势

【触想智能】工控一体机与5G物联网技术结合是未来发展趋势

工控一体机也叫工业电脑一体机&#xff0c;是工业应用非常重要的一种产品。目前&#xff0c;工控一体机在工业领域的应用已经非常普及&#xff0c;在繁忙的生产车间、数字化机床、自助服务终端设备等场景中&#xff0c;我们都有看到它的身影。 工控一体机应用的普及已经潜移默化…
阅读更多...
InstructionGPT

InstructionGPT

之前是写在[Instruction-tuning&#xff08;指令微调&#xff09;]里的&#xff0c;抽出来单独讲一下。 基本原理 在做下游的任务时&#xff0c;我们发现GPT-3有很强大的能力&#xff0c;但是只要人类说的话不属于GPT-3的范式&#xff0c;他几乎无法理解。例如&#xff0c;我们…
阅读更多...
华为---DHCP中继代理简介及示例配置

华为---DHCP中继代理简介及示例配置

DHCP中继代理简介 IP动态获取过程中&#xff0c;客户端&#xff08;DHCP Client&#xff09;总是以广播&#xff08;广播帧及广播IP报文&#xff09;方式来发送DHCPDISCOVER和DHCPREQUEST消息的。如果服务器&#xff08;DHCP Server&#xff09;和 客户端不在同一个二层网络(二…
阅读更多...
通过el-tree 懒加载树，创建国家地区四级树

通过el-tree 懒加载树，创建国家地区四级树

全国四级行政地区树数据库sql下载路径&#xff1a;【免费】全国四级地区(省市县)数据表sql资源-CSDN文库https://download.csdn.net/download/weixin_51722520/88469807?spm1001.2014.3001.5503 我在后台获取地区信息添加了限制&#xff0c;只获取parentid为当前的地…
阅读更多...
Gloss优化

Gloss优化

Gloss优化&#xff0c;Route – Gloss – Parameters .清除不必要的线和过孔&#xff0c;圆滑线&#xff0c;焊盘中间的线&#xff0c;把转角变成圆弧&#xff0c;自动布线总会产生一些布线效果不好、多余过孔等问题。此时可以利用allegro提供的Gloss命令对设计进行优化和调整&…
阅读更多...
ES6新增循环对象的四种方法(通俗易懂)

ES6新增循环对象的四种方法(通俗易懂)

在我们ES6之前&#xff0c;我们一般都是用for…in来循环对象&#xff0c;现在我们ES6为我们新增了几种方法&#xff0c;让我为大家介绍一下吧&#xff01; 1.Object.keys() 静态方法返回一个由给定对象自身的可枚举的字符串键属性名组成的数组 const obj {name:"zs&quo…
阅读更多...
项目部署Linux步骤

项目部署Linux步骤

1、最小化安装centos7-环境准备 安装epel-release 安装epel-release&#xff0c;因为有些rpm包在官方库中找不到。前提是保证可以联网 yum install -y epel-release 修改IP net-tools net-tool&#xff1a;工具包集合&#xff0c;包含ifconfig等命令 yum install -y net-…
阅读更多...
最新文章

Copyright @ 2022~2023