【Linux】进程程序替换 做一个简易的shell

提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档

目录

文章目录

前言

进程程序替换

替换原理

先看代码和现象

替换函数

第一个execl():

第二个execv():

第三个execvp():

第四个execvpe():

环境变量

第五个execlp():

第六个execle():

函数解释

命名理解

在Makefile中形成两个可执行程序

方法一:

方法二:

做一个简易的shell

总结



前言

世上有两种耀眼的光芒,一种是正在升起的太阳,一种是正在努力学习编程的你!一个爱学编程的人。各位看官,我衷心的希望这篇博客能对你们有所帮助,同时也希望各位看官能对我的文章给与点评,希望我们能够携手共同促进进步,在编程的道路上越走越远!


提示:以下是本篇文章正文内容,下面案例可供参考

进程程序替换

替换原理

用fork()创建子进程后执行的是和父进程相同的程序(但有可能执行不同的代码分支),子进程往往要调用一种exec系列的函数以执行另一个程序。当进程调用一种exec系列的函数时,该进程的用户空间代码和数据完全被新程序替换,从新程序的启动例程开始执行。调用exec并不创建新进程,所以调用exec前后该进程的pid并未改变。

其实是操作系统将磁盘设备里的代码和数据加载到内存设备上了,也就是说exec系列的函数是系统调用接口或者exec系列的函数底层由系统调用。

先看代码和现象

#include <stdio.h>
#include <unistd.h>

int main()
{
	printf("testexec ... begin!\n");

	execl("/usr/bin/ls", "ls", "-l", "-a", NULL);

	printf("testexec ... end!\n");
	return 0;
}

  • 用exec系列的函数执行起来新的程序。
  • exec系列的函数,执行完毕之后,后续的代码不见了,因为被替换了。
  • execl函数的返回值可以不用关心,只要替换成功,就不会向后继续运行;只要继续运行了,一定是替换失败了!

fork()创建子进程,让子进程自己去替换。

创建子进程,让子进程完成任务:1、让子进程执行父进程代码的一部分;2、让子进程执行一个全新的程序。

父进程创建一个子进程,子进程继承父进程的代码和数据,子进程刚开始的时候,用的是和父进程一样的代码和数据;但是当子进程中用exec系列函数执行新的进程时,会让新进程的代码和数据替换原来的代码和数据,不过因为各个进程之间都有独立性,所以,OS发生写实拷贝,将代码和数据复制一份,放入新申请的空间内,重新建立映射关系。

替换函数

其实有六种以exec开头的函数,统称exec函数:

#include <unistd.h>

第一个execl():

int execl(const char *path, const char *arg, ...);
  • 第一个参数:path:我们要执行的程序,需要带路径(怎么找到程序,你得告诉我)
  • 第二个参数:可变参数列表(命令行中怎么执行,你就怎么传参),并以NULL结尾

举一个例子:

execl("/usr/bin/ls", "ls", "-a", "-i", "-l", NULL);

第二个execv():

 int execv(const char *path, char *const argv[]);
  • 第一个参数:path:我们要执行的程序,需要带路径(怎么找到程序,你得告诉我)
  • 第二个参数:命令行参数列表(指针数组,数组当中的内容表示你要如何执行这个程序),指针数组要以NULL结尾

举一个例子:

char *const argv[] = 
{
   (char*)"ls",
   (char*)"-a",
   (char*)"-b",
   NULL
};

execv("/usr/bin/ls", argv);

第三个execvp():

int execvp(const char *file, char *const argv[]);
  • 第一个参数:用户可以不传要执行的文件的路径(但是文件名要传),直接告诉exec系列的函数,我要执行谁就行(注:查找这个程序,系统会自动在环境变量PATH中进行查找)。
  • 第二个参数:命令行参数列表(指针数组,数组当中的内容表示你要如何执行这个程序),指针数组要以NULL结尾。

举一个例子:

char *const argv[] = 
{
   (char*)"ls",
   (char*)"-a",
   (char*)"-b",
   NULL
};

execvp("ls", argv);

第四个execvpe():

int execvpe(const char *file, char *const argv[], char *const envp[]);
  • 第一个参数:用户可以不传要执行的文件的路径(但是文件名要传),直接告诉exec系列的函数,我要执行谁就行(注:查找这个程序,系统会自动在环境变量PATH中进行查找)。
  • 第二个参数:命令行参数列表(指针数组,数组当中的内容表示你要如何执行这个程序),指针数组要以NULL结尾。
  • 第三个参数:环境变量表。
环境变量
  • 1、用老的环境变量给子进程,environ;
char *const argv[] = 
{
   (char*)"mypragma",
   (char*)"-a",
   (char*)"-b",
   NULL
};

extern char**environ;

execvpe("./mypragma", argv, environ);
  • 2、自定义环境变量:整体替换所有的环境变量
char *const argv[] = 
{
   (char*)"mypragma",
   (char*)"-a",
   (char*)"-b",
   NULL
};

char *const envp[] =
{
   (char*)"HAHA=111111",
   (char*)"HEHE=222222",
   NULL
};

execvpe("./mypragma", argv, environ);
  • 3、把老的环境变量稍加修改,给子进程
putenv("HHHH=111111111111111111");
// 将HHHH变量添加到当前进程的环境变量表里

// 我的父进程main()本身就有一批环境变量!!!, 从bash来

char *const argv[] = 
{
   (char*)"mypragma",
   (char*)"-a",
   (char*)"-b",
   NULL
};

execvpe("./mypragma", argv, environ);

第五个execlp():

int execlp(const char *file, const char *arg, ...);

第六个execle():

 int execle(const char *path, const char *arg, ...,char *const envp[]);

函数解释

  • 这些函数如果调用成功则加载新的程序从启动代码开始执行,不再返回。
  • 如果调用出错则返回-1
  • 所以exec函数只有出错的返回值而没有成功的返回值。

命名理解

这些函数原型看起来很容易混,但只要掌握了规律就很好记。

  • l(list) : 表示参数采用列表
  • v(vector) : 参数用数组
  • p(path) : 有p自动搜索环境变量PATH
  • e(env) : 表示自己维护环境变量
函数名参数格式是否带路径是否使用当前环境变量
execl列表
execlp列表
execle列表否,需自己组装环境变量
execv数组
execvp数组
execve数组否,需自己组装环境变量

2号手册是系统调用接口 。
我们说的exec系列的函数不是2号手册(系统调用),而是三号手册。
exec系列的函数实际上是在C语言层面上做了一个简单的封装。

int execve(const char* path, char* const argv[], char* const envp[]); 
//2号手册

事实上,只有execve才是真正的系统调用,其它五个函数最终都是调用的execve,所以execve在man手册的第2节,而其它五个函数在man手册的第3节,也就是说其他五个函数实际上是对系统调用execve进行了封装,以满足不同用户的不同调用场景的。

下图为exec系列函数族之间的关系:

在Makefile中形成两个可执行程序

方法一:

Makefile在形成的时候,默认从上到下匹配时,只会默认形成第一个目标文件所对应的可执行程序,所以,我们要把Makefile文件中的两个程序倒一下,才能形成第二个可执行程序。

方法二:

那我们想要在Makefile中一次性形成两个可执行程序该怎么办呢?
我们可以定义一个尾目标,尾目标后面跟着两个可执行程序的名字。尾目标有依赖关系,不写依赖方法。

.PHONY:all
all : testexec mypragma

testexec : testexec.c
    gcc - o $@ $ ^
mypragma:mypragma.cc
     g++ - o $@ $ ^ -std = c++11
.PHONY:clean
clean :
     rm - f testexec mypragma

所有的脚本语言都要有一个对应的解释器(python、bash等)。解释器本身使用C/C++写的。
解释器就相当于一个可执行程序。
python3 test.py   // test.py:命令行参数,它就是一个文件;  
解释器会将命令行参数传进来,就知道解释器要解释那个文件了,在解释器的代码中将文件test.py打开,然后会一行一行解释。

做一个简易的shell

考虑下面这个与shell典型的互动:

[root@localhost epoll]# ls
client.cpp  readme.md  server.cpp  utility.h
[root@localhost epoll]# pwd
   PID TTY          TIME CMD
3451 pts / 0    00:00 : 00 bash
3514 pts / 0    00 : 00 : 00 pwd

用下图的时间轴来表示事件的发生次序。其中时间从左向右。shell由标识为sh的方块代表,它随着时间的流逝从左向右移动。shell从用户读入字符串"ls"。shell建立一个新的进程,然后在那个进程中运行ls程序并等待那个进程结束。

然后shell读取新的一行输入,建立一个新的进程,在这个进程中运行程序并等待这个进程结束。 所以要写一个shell,需要循环以下过程:

  1. 获取命令行
  2. 解析命令行
  3. 建立一个子进程(fork)
  4. 替换子进程(execvp)
  5. 父进程等待子进程退出(wait)

根据这些思路,和我们前面的学的技术,就可以自己来实现一个shell了。

命令行(命令行解释器、bash、父进程)本质上就是一个输出的字符串: [root@localhost epoll]# root:用户 localhost:主机名 epoll:路径
 

#define _CRT_SECURE_NO_WARNINGS 1

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/wait.h>

#define SIZE 512  // 在缓冲区定义一个命令行字符串
#define ZERO '\0'
#define SEP " "   // 定义分隔符为空格,分隔符为空格字符串 ----> strtok
#define NUM 32    // 定义指针数组(命令行参数标)当前有几个元素:命令 + 选项
// 写宏函数时,如果有代码块,一般建议放入do{ .... }while(0)里
#define SkipPath(p) do{ p += (strlen(p)-1); while(*p != '/') p--; }while(0)


// 环境变量本身就需要我们单独维护的
// 为了方便,我就直接定义环境变量,环境变量是cwd:当前的工作路径(缓冲区)
char cwd[SIZE * 2];
char* gArgv[NUM];
int lastcode = 0;// 退出码

// 子进程创建失败,死去了
void Die()
{
    exit(1);
}

// 返回用户家目录
const char* GetHome()
{
    const char* home = getenv("HOME");
    if (home == NULL) return "/";
    return home;
}

// 获取用户名
const char* GetUserName()
{
    // getenv():根据环境变量名,得到环境变量的内容
    const char* name = getenv("USER");
    // 成功:返回环境变量的内容(字符串)  失败:返回NULL
    if (name == NULL) 
        return "None";
    return name;
}

// 获取当前的主机名
const char* GetHostName()
{
    const char* hostname = getenv("HOSTNAME");
    if (hostname == NULL) 
        return "None";
    return hostname;
}
// 临时 获取当前的工作路径(有坑的)
const char* GetCwd()
{
    const char* cwd = getenv("PWD");
    if (cwd == NULL) return "None";
    return cwd;
}

// 做一个命令行
// commandline : output输出型参数,我们像通过commandline把我们的命令行字符串获取出来
void MakeCommandLineAndPrint()
{
    char line[SIZE];// 定义一个命令行字符串的缓冲区
    const char* username = GetUserName();
    const char* hostname = GetHostName();
    const char* cwd = GetCwd();

    // 我们想要获取当前路径的最后一块路径
    SkipPath(cwd);
    // 更安全的进行把指定参数按照特定格式写入到指定长度的缓冲区当中
    snprintf(line, sizeof(line), "[%s@%s %s]> ", username, hostname, strlen(cwd) == 1 ? "/" : cwd + 1);// cwd+1:最后一个/的下一个位置
    // 第三个参数特殊处理了一下,当只剩最后一个"/"时,打印出来
    printf("%s", line);
    fflush(stdout);// 把标准输出显示一下命令行
}

// 获取用户命令
int GetUserCommand(char command[], size_t n)
{
    // 从键盘中输入命令放入指定的缓存区中,缓存区大小为n
    char* s = fgets(command, n, stdin);
    if (s == NULL) return -1;
    // 假设我们输入的字符串abcd,我们按回车就相当于换行(\n),
    // 此时字符串为abcd\n,五个字符,5-1下标为4,我们将下标为4的赋值为\0
    command[strlen(command) - 1] = ZERO;
    return strlen(command);// 获得命令有几个字符
}


void SplitCommand(char command[], size_t n)
{
    (void)n;
    // "ls -a -l -n" -> "ls" "-a" "-l" "-n"
    gArgv[0] = strtok(command, SEP);
    int index = 1;
    while ((gArgv[index++] = strtok(NULL, SEP))); // done, 故意写成=,表示先赋值,在判断. 分割之后,strtok会返回NULL,刚好让gArgv最后一个元素是NULL, 并且while判断结束
}

void ExecuteCommand()
{
    pid_t id = fork();
    if (id < 0) Die();
    else if (id == 0)
    {
        // child
        execvp(gArgv[0], gArgv);
        exit(errno);
    }
    else
    {
        // fahter
        int status = 0;
        pid_t rid = waitpid(id, &status, 0);
        if (rid > 0)
        {
            lastcode = WEXITSTATUS(status);
            if (lastcode != 0) printf("%s:%s:%d\n", gArgv[0], strerror(lastcode), lastcode);
        }
    }
}

void Cd()
{
    const char* path = gArgv[1];
    // 返回用户家目录
    if (path == NULL) 
        path = GetHome();
    // path 一定存在
    // 切换一个进程的路径,进程的当前路径
    chdir(path);

    // 如果当前所在的路径发生变化了,一定要对环境变量更新,否则命令行解释器上的路径不会发生变化
    // 环境变量本来就是让父进程bash来维护的:导环境变量
    // 刷新环境变量
    char temp[SIZE * 2];// temp:临时的缓冲区
    getcwd(temp, sizeof(temp));// 重新获取绝对路径
    // 我们要导环境变量,就得把路径给刷新一下
    // 更安全的进行把指定参数按照特定格式写入到指定长度的缓冲区当中
    snprintf(cwd, sizeof(cwd), "PWD=%s", temp);// 我们每一次要刷新PWD环境变量时,我们都要采用绝对路径
    // putenv语意:存在就更新,不存在就设置
    putenv(cwd); // OK
}

int CheckBuildin()
{
    int yes = 0;// 假设当前命令不是内建命令
    // 用户输入的命令
    const char* enter_cmd = gArgv[0];
    if (strcmp(enter_cmd, "cd") == 0)
    {
        yes = 1;
        Cd();
    }
    else if (strcmp(enter_cmd, "echo") == 0 && strcmp(gArgv[1], "$?") == 0)
    {
        yes = 1;
        printf("%d\n", lastcode);
        lastcode = 0;
    }
    return yes;
}

int main()
{
    int quit = 0;
    // 让命令行一直执行下去
    while (!quit)
    {
        // 1. 我们需要自己输出一个命令行
        MakeCommandLineAndPrint();

        // 2. 获取用户命令字符串
        char usercommand[SIZE];// 定义一个用户命令字符串usercommand的缓冲区
        int n = GetUserCommand(usercommand, sizeof(usercommand));
        if (n <= 0) 
            return 1;
        // 这里也不会存在越界的问题
        // 假设我们输入的字符串abcd,我们按回车就相当于换行(\n),此时字符串为abcd\n,五个字符,5-1下标为4,我们将下标为4的赋值为\0
        usercommand[strlen(usercommand) - 1] = ZERO;

        // 3. 命令行字符串分割. 
        SplitCommand(usercommand, sizeof(usercommand));

        // 4. 检测命令是否是内建命令
        n = CheckBuildin();
        if (n) continue;
        // 5. 执行命令
        ExecuteCommand();
    }
    return 0;
}

当时我们讲的故事:命令行解释器就是bash(王婆),王婆给别人做命令行解释,把命令交给操作系统,通过程序替换的方式交给操作系统。

#include <stdio.h>
// 按行获取

char *fgets(char *s,int size,FILE *stream);
// 按行进行从特定的文件流当中获取指定的内容,指定的内容放在s指向的缓冲区,缓冲区的大小是size。
// 成功:返回值是s指向缓冲区的起始地址  失败:返回NULL

每个进程都会记录当前所处的路径,父进程和子进程都分别有属于自己的路径。
我们今天实现的shell,执行任何命令,都是要执行fork()创建子进程的,所以,当我们在shell中执行 cd .. 命令的时候,是让子进程去执行去了,子进程把自己的路径切换了,但和当前的bash没有关系。
命令行是属于父进程bash的,所以, cd .. 这样的命令应该让父进程去执行。
要让父进程执行的命令,我们叫做内建命令

// 切换一个进程的路径 man chdir 系统调用
int chdir(const char *path)
// man getcwd :获取一下当前的工作目录;所以不管修改的是绝对路径,还是相对路径,重新获取一下,就是绝对路径
char *getcwd(char *buf,size_t size)

总结

好了,本篇博客到这里就结束了,如果有更好的观点,请及时留言,我会认真观看并学习。
不积硅步,无以至千里;不积小流,无以成江海。

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

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

相关文章

【MySQL】DQL-查询语句全解 [ 基础/条件/分组/排序/分页查询 ](附带代码演示&案例练习)

前言 大家好吖&#xff0c;欢迎来到 YY 滴MySQL系列 &#xff0c;热烈欢迎&#xff01; 本章主要内容面向接触过C Linux的老铁 主要内容含&#xff1a; 欢迎订阅 YY滴C专栏&#xff01;更多干货持续更新&#xff01;以下是传送门&#xff01; YY的《C》专栏YY的《C11》专栏YY的…

瑞吉外卖实战学习--8、人员禁用和启用

前言 1、通过前端页面查看接口 会发现请求方式是put 请求接口是employee 2、检查页面传值 根据浏览器的请求可以看到传值为id和status 2、写put请求&#xff0c;添加修改时间和修改人的id然后传回给后台 /*** 启用和禁用员工账号* param request* param employee* return…

为何有时坚持很苦,而有时坚持很酷

坚持很苦 大部分情况下是被动的&#xff0c;被迫的&#xff0c;坚持去做的事情并不是自己发自内心的。 比如一部分学生考研或者读书&#xff0c;都是随大流盲从而已&#xff0c;自己想做啥都不清楚。 坚持很酷 追求自己的理想是这个蓝色星球上最酷炫的事情啦&#xff0c;没有…

二维码门楼牌管理应用平台建设:实现智能化与人性化的数据治理

文章目录 前言一、二维码门楼牌管理应用平台的建设背景二、人工数据审核的重要性三、地址匹配校验的实现四、人工修正的流程与机制五、人工数据审核的挑战与对策六、展望未来 前言 在数字化时代的浪潮下&#xff0c;二维码门楼牌管理应用平台的建设成为了城市管理的新宠。本文…

【嵌入式智能产品开发实战】(七)—— 政安晨:通过ARM-Linux掌握基本技能【环境准备:树莓派】

目录 Raspberry Pi OS 下载系统镜像 使用SSH客户端登陆 升级更新 政安晨的个人主页&#xff1a;政安晨 欢迎 &#x1f44d;点赞✍评论⭐收藏 收录专栏: 嵌入式智能产品开发实战 希望政安晨的博客能够对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提出指正…

详解Linux进程

进程 1.什么是进程2.创建进程2.1进程标识符2.2初时fork&#xff08;&#xff09;函数&#xff0c;创建进程 3.进程状态3.1进程状态的描述3.2Linux中具体的进程状态 4 僵尸状态5 孤儿进程6进程优先级 1.什么是进程 进程在我们的电脑和手机上是无处不在的。例如我们windows系统下…

基于SpringBoot+Vue前后端分离的停车场管理系统设计与实现+毕业论文(12000字)

介绍 本系统主要包含普通用户与管理员两个用户角色&#xff1a;普通用户功能模块&#xff1a;可以方便地对车位进行查询&#xff0c;车位申请和个人缴费。 管理员功能模块: 管理系统用户&#xff0c;停车位&#xff0c;用户缴费信息管理&#xff0c;登录日志管理。 普通用户…

白色微立体的智能界面,就喜欢这种简洁白净。

本次发一些微立体风格的智能家居界面&#xff0c;风格为微立体&#xff0c;也叫轻拟物风格&#xff0c;或者新拟态风格。

25Ramdisk 启动模式简介

Ramdisk 启动模式简介 ramdisk是一种虚拟磁盘技术,我们的PE系统几乎都是使用ramdisk方式从计算机启动的.那么,ramdisk有哪些特点呢? Ramdisk 将内存虚拟为一个磁盘 Ramdisk技术会将你的一部分内存虚拟成一块磁盘分区.使用U盘启动pe系统时,打开pe系统里的文件资源管理器,你会看…

(文章复现)考虑分布式电源不确定性的配电网鲁棒动态重构

参考文献&#xff1a; [1]徐俊俊,吴在军,周力,等.考虑分布式电源不确定性的配电网鲁棒动态重构[J].中国电机工程学报,2018,38(16):4715-47254976. 1.摘要 间歇性分布式电源并网使得配电网网络重构过程需要考虑更多的不确定因素。在利用仿射数对分布式电源出力的不确定性进行合…

云防护是怎么能帮助用户做好网络安全

在数字化时代&#xff0c;网络安全威胁呈现出愈发复杂和多样化的趋势。 无论是个人用户、小型企业还是大型企业&#xff0c;都面临着来自全球各地的网络攻击风险。这些攻击可能导致数据泄露、服务中断、财务损失甚至声誉受损。因此&#xff0c;采取有效的安全防护措施变得至关…

数据处理的两个基本问题

文章目录 数据处理的两个基本问题bx、si、di、bp机器指令处理的数据所在位置汇编语言中数据位置的表达寻址方式指令要处理的数据有多长&#xff1f;div 指令伪指令 dddup 数据处理的两个基本问题 我们知道&#xff0c;计算机是进行数据处理、运算的机器&#xff0c;那么有两个基…

基于Tampermonkey 实现自动答题和视频播放

目录 一、环境准备 二、下载Tampermonkey 三、安装脚本 四、启用脚本 一、环境准备 微软自带的 edge 浏览器(电脑端) 二、下载Tampermonkey 安装地址&#xff1a;Tampermonkey 篡改猴(油猴脚本) 下载完成会在浏览器拓展中自动生成一个插件&#xff0c;此时点击管理拓展&…

linux 内核模块入门

内核模块可以动态地被安装到内核&#xff0c;从而扩展内核的功能&#xff0c;使用内核模块时不需要重新编译内核。内核模块常用的场景是驱动&#xff0c;随着芯片种类的增加&#xff0c;硬件种类的增加&#xff0c;这些芯片或者硬件(比如网卡) 的驱动可以以模块的方式进行开发&…

ONT60 旋转链表 思路分享

题干链接&#xff1a;ONT60 旋转链表 ​ 这道题是反转链表题的pro升级版&#xff0c;但比反转链表略微复杂一些。如果有做过旋转数组那道题&#xff08;链接在这里&#xff1a;https://blog.csdn.net/wyd_333/article/details/126712919&#xff0c;但当时刷这道题的时候我用的…

Linux|centos7-postgresql数据库|yum安装数据库和配置repmgr高可用集群以及repmgr的日常管理工作

一、 前言 postgresql 的yum部署其实还是有点东西的&#xff0c;本文就做一个小小的记录&#xff0c;高可用方面repmgr插件还是非常不错的&#xff0c;但如何部署以及部署后如何使用也是一个难点&#xff0c;因此&#xff0c;也在本文里做一个记录 环境介绍&#xff1a; 第…

【Redis教程0x0A】详解Redis哨兵机制

1. 引言 Redis的哨兵机制是基于主从架构的。 在 Redis 的主从架构中&#xff0c;由于主从模式是读写分离的&#xff0c;如果主节点&#xff08;master&#xff09;挂了&#xff0c;那么将没有主节点来服务客户端的写操作请求&#xff0c;也没有主节点给从节点&#xff08;slav…

java: 错误: 无效的源发行版:17

目录 一、java: 错误: 无效的源发行版&#xff1a;17 报错 原因 解决方法 二、pring-boot-starter-parent下面的版本报红 原因 解决方案 一、java: 错误: 无效的源发行版&#xff1a;17 报错 创建了一个sprintboot项目&#xff0c;运行CommunityApplication时&#xf…

小白从0学习ctf(web安全)

文章目录 前言一、baby lfi&#xff08;bugku-CTF&#xff09;1、简介2、解题思路1、解题前置知识点2、漏洞利用 二、baby lfi 2&#xff08;bugku-CTF&#xff09;1.解题思路1、漏洞利用 三、lfi&#xff08;bugku CTF&#xff09;1、解题思路1、漏洞利用 总结 前言 此文章是…

动态规划刷题(算法竞赛、蓝桥杯)--合唱队形(线性DP)

1、题目链接&#xff1a;[NOIP2004 提高组] 合唱队形 - 洛谷 #include <bits/stdc.h> using namespace std; int n,ans; int a[105],f[105][2];//f[i][2]中2表示正反两个方向int main(){cin>>n;for(int i1;i<n;i){cin>>a[i];}//正方向求最长上升子序列 a[…