DP(动态规划)【2】 最大连续子列和 最长不降子序列

1.最大连续子列和

#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <cstring>
#include <queue>
using namespace std;
const int N=10002,maxn=10;int n,m,k,f[N]={0},dp[N]={0};


int main()
{scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%d",&f[i]);
//一定要以i结尾!! 
dp[0]=f[0];
int ans=f[0];
	for(int i=1;i<n;i++)
	{
	dp[i]=max(f[i],dp[i-1]+f[i]);
	if(dp[i]>ans) ans=dp[i];
	}
//	for(int i=1;i<n;i++)

printf("%d",ans);
}

 输出最大方案

这样写是不对的,只在dp[i]>ans才更新ans_i,举个例子

1,-2,0.5,1

导致ans_i=0

#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <cstring>
#include <queue>
using namespace std;
const int N=10002,maxn=10;int n,m,k,f[N]={0},dp[N]={0};


int main()
{scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%d",&f[i]);
//一定要以i结尾!! 
dp[0]=f[0];
int ans=f[0];
int ans_i=0;
int ans_j=0;
	for(int i=1;i<n;i++)
	{
	dp[i]=max(f[i],dp[i-1]+f[i]);
	if(dp[i]>ans)
	{
		ans=dp[i];ans_j=i;
		if(dp[i-1]<0) ans_i=i;
	 } 
	}
//	for(int i=1;i<n;i++)

printf("%d %d %d",ans,ans_i+1,ans_j+1);
}

由于少了一句话一直在错,加上就对了

#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <cstring>
#include <queue>
using namespace std;
const int N=10002,maxn=10;int n,m,k,f[N]={0},dp[N]={0};


int main()
{scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%d",&f[i]);
//一定要以i结尾!! 
dp[0]=f[0];
int ans=f[0];
int ans_i=0;
int ans_j=0;
int ans_i2=0;
	for(int i=1;i<n;i++)
	{
		
		if(dp[i-1]<0)
		{ans_i=i;dp[i]=f[i];
		if(dp[i]>ans)
		{ans=dp[i];ans_i2=ans_i;ans_j=i;
		}
	}
		else
		{dp[i]=f[i]+dp[i-1];
		if(dp[i]>ans)
		{ans=dp[i];ans_j=i;
        ans_i2=ans_i;//就缺这句话!
		}
		}
}
//	dp[i]=max(f[i],dp[i-1]+f[i]);
//	if(dp[i]>ans)
//	{
//		ans=dp[i];ans_j=i;
//		if(dp[i-1]<0) ans_i=i;
//	 } 
//	}
//	for(int i=1;i<n;i++)

printf("%d %d %d",ans,ans_i2+1,ans_j+1);
}

答案

用了一个数组存储以i为结尾的start

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

const int MAXN = 10000;
int a[MAXN];
int dp[MAXN], start[MAXN];

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    dp[0] = a[0];
    start[0] = 0;
    for (int i = 1; i < n; i++) {
        if (dp[i - 1] >= 0) {
            dp[i] = dp[i - 1] + a[i];
            start[i] = start[i - 1];
        } else {
            dp[i] = a[i];
            start[i] = i;
        }
    }
    int k = 0;
    for (int i = 1; i < n; i++) {
        if (dp[i] > dp[k]) {
            k = i;
        }
    }
    printf("%d %d %d", dp[k], start[k] + 1, k + 1);
    return 0;
}

难点:如何设计状态状态转移方程

本题

状态 取:以第i位结尾的连续子序列最大和

2.最长不降子序列

如果要用枚举,复杂度2^n

状态:以第i个数结尾的序列长度dp[i]

状态转移方程:

#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <cstring>
#include <queue>
using namespace std;
const int N=10002,maxn=10;int n,m,k,f[N]={0},dp[N]={0};


int main()
{scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%d",&f[i]);
//一定要以i结尾!! 
dp[0]=1;
int temp=1;
int ans=1;
	for(int i=1;i<n;i++)
	{temp=1;
		for(int j=0;j<i;j++)
		{if(f[i]>=f[j])
		{
			if(dp[j]+1>temp){temp=dp[j]+1;//dp[i]=temp;
			}
		}
		}
		dp[i]=temp;
		if(ans<temp) ans=temp;
		
	}
//	for(int i=1;i<n;i++)

printf("%d",ans);
}

写完发现,temp其实是多余的)

输出最大方案

#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <cstring>
#include <queue>
using namespace std;
const int N=10002,maxn=10;int n,m,k,f[N]={0},dp[N]={0};


int main()
{scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%d",&f[i]);
//一定要以i结尾!! 
dp[0]=1;
int temp=1;
int ans=1;
//int l=0,r=0;
int anslist[n]={0};
int lst=0;
	for(int i=1;i<n;i++)
	{temp=1;
		for(int j=0;j<i;j++)
		{if(f[i]>=f[j])
		{
			if(dp[j]+1>temp){temp=dp[j]+1;anslist[i]=j;
			}
		}
		}
		dp[i]=temp;
		if(ans<temp) 
		{		ans=temp;lst=i;//寻址 
		

		}
		
	}
//	for(int i=1;i<n;i++)

//printf("%d",dp[i]);
printf("%d\n",ans);
int p[n];int k=0,t=lst;
p[0]=f[lst];
while(t>0)
{//k++;
if(anslist[t]==0)
{if(p[k]>=f[0])
{k++;t=anslist[t];p[k]=f[t];
}
else t=0;

}
else
{k++;
t=anslist[t];
p[k]=f[t];
}

}
for(int i=k;i>=0;i--)
{printf("%d",p[i]); if(i>0) printf(" ");

}

}

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

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

相关文章

1.SQL注入-数字型

SQL注入-数字型(post) 查询1的时候发现url后面的链接没有传入1的参数。验证为post请求方式&#xff0c;仅显示用户和邮箱 通过图中的显示的字段&#xff0c;我们可以猜测传入数据库里面的语句&#xff0c;例如&#xff1a; select 字段1,字段2 from 表名 where id1; 编辑一个…

【漏洞复现】宏景HCM人力资源信息管理系统——任意文件读取漏洞

声明&#xff1a;本文档或演示材料仅供教育和教学目的使用&#xff0c;任何个人或组织使用本文档中的信息进行非法活动&#xff0c;均与本文档的作者或发布者无关。 文章目录 漏洞描述漏洞复现测试工具 漏洞描述 宏景HCM人力资源信息管理系统是一款全面覆盖人力资源管理各模块…

GPT-4o首次引入!全新图像自动评估基准发布!

目录 01 什么是DreamBench&#xff1f; 02 与人类对齐的自动化评估 03 更全面的个性化数据集 04 实验结果 面对层出不穷的个性化图像生成技术&#xff0c;一个新问题摆在眼前&#xff1a;缺乏统一标准来衡量这些生成的图片是否符合人们的喜好。 对此&#xff0c;来自清华大…

心理辅导平台系统

摘 要 中文本论文基于Java Web技术设计与实现了一个心理辅导平台。通过对国内外心理辅导平台发展现状的调研&#xff0c;本文分析了心理辅导平台的背景与意义&#xff0c;并提出了论文研究内容与创新点。在相关技术介绍部分&#xff0c;对Java Web、SpringBoot、B/S架构、MVC模…

lvs+上一章的内容

书接上回这次加了个keepalived 一、集群与分布式 1.1 集群介绍 **集群&#xff08;Cluster&#xff09;**是将多台计算机组合成一个系统&#xff0c;以解决特定问题的计算机集合。集群系统可以分为以下三种类型&#xff1a; **LB&#xff08;Load Balancing&#xff0c;负载…

Golang | Leetcode Golang题解之第203题移除链表元素

题目&#xff1a; 题解&#xff1a; func removeElements(head *ListNode, val int) *ListNode {dummyHead : &ListNode{Next: head}for tmp : dummyHead; tmp.Next ! nil; {if tmp.Next.Val val {tmp.Next tmp.Next.Next} else {tmp tmp.Next}}return dummyHead.Next …

【2024最新华为OD-C/D卷试题汇总】[支持在线评测] 数字排列游戏(200分) - 三语言AC题解(Python/Java/Cpp)

&#x1f36d; 大家好这里是清隆学长 &#xff0c;一枚热爱算法的程序员 ✨ 本系列打算持续跟新华为OD-C/D卷的三语言AC题解 &#x1f4bb; ACM银牌&#x1f948;| 多次AK大厂笔试 &#xff5c; 编程一对一辅导 &#x1f44f; 感谢大家的订阅➕ 和 喜欢&#x1f497; &#x1f…

【论文复现】——基于LM优化的NDT点云配准算法

目录 一、算法原理1、论文概述2、参考文献二、代码实现三、结果展示本文由CSDN点云侠原创,原文链接,爬虫自重。如果你不是在点云侠的博客中看到该文章,那么此处便是不要脸的爬虫与GPT生成的文章。 一、算法原理 1、论文概述 传统的正态分布变换配准算法处理初始位姿变换相…

修改网络的结构用于预训练

目录 一、模型准备 二、修改结构 1、在网络中添加一层 2、在classifier结点添加一个线性层 3、修改网络中的某一层(features 结点举例&#xff09; 4、替换网络中的某一层结构&#xff08;与第3点类似&#xff09; 5、提取全连接层的输入特征数和输出特征数 6、删除网络…

springboot + Vue前后端项目(第二十一记)

项目实战第二十一记 写在前面1. springboot文件默认传输限制2. 安装视频插件包命令3. 前台Video.vue4. 创建视频播放组件videoDetail.vue5. 路由6. 效果图总结写在最后 写在前面 本篇主要讲解系统集成视频播放插件 1. springboot文件默认传输限制 在application.yml文件中添…

《昇思25天学习打卡营第2天|快速入门》

文章目录 前言&#xff1a;今日所学&#xff1a;1. 数据集处理2. 网络的构建3. 模型训练4. 保存模型5. 加载模型 总体代码与运行结果&#xff1a;1. 总体代码2. 运行结果 前言&#xff1a; 今天是学习打卡的第2天&#xff0c;今天的内容是对MindSpore的一个快速入门&#xff0…

Selenium IDE 的使用指南

Selenium IDE 的使用指南 在自动化测试的领域中&#xff0c;Selenium 是一个广为人知且强大的工具集。而 Selenium IDE 作为其中的一个组件&#xff0c;为测试人员提供了一种便捷且直观的方式来创建和执行自动化测试脚本。 一、Selenium IDE 简介 Selenium IDE 是一个用于录…

第十三章 常用类

一、包装类 1. 包装类的分类 &#xff08;1&#xff09;针对八种基本数据类型相应的引用类型—包装类 &#xff08;2&#xff09;有了类的特点&#xff0c;就可以调用类中的方法。 2. 包装类和基本数据的转换 jdk5 前的手动装箱和拆箱方式&#xff0c;装箱&#xff1a;基本…

【Qt】信号和槽机制

创作不易&#xff0c;本篇文章如果帮助到了你&#xff0c;还请点赞 关注支持一下♡>&#x16966;<)!! 主页专栏有更多知识&#xff0c;如有疑问欢迎大家指正讨论&#xff0c;共同进步&#xff01; &#x1f525;c系列专栏&#xff1a;C/C零基础到精通 &#x1f525; 给大…

操作系统之《PV操作》【知识点+详细解题过程】

1、并发进程 &#xff1a; 并发的实质是一个处理器在几个进程之间的多路复用&#xff0c;并发是对有限的物理资源强制行使多用户共享&#xff0c;消除计算机部件之间的互等现象&#xff0c;以提高系统资源利用率。 &#xff08;1&#xff09;并发进程——互斥性&#xff1a; 进…

使用Jetpack Compose实现具有多选功能的图片网格

使用Jetpack Compose实现具有多选功能的图片网格 在现代应用中,多选功能是一项常见且重要的需求。例如,Google Photos允许用户轻松选择多个照片进行分享、添加到相册或删除。在本文中,我们将展示如何使用Jetpack Compose实现类似的多选行为,最终效果如下: 主要步骤 实现…

【redis】Redis AOF

1、AOF的基本概念 AOF持久化方式是通过保存Redis所执行的写命令来记录数据库状态的。AOF以日志的形式来记录每个写操作&#xff08;增量保存&#xff09;&#xff0c;将Redis执行过的所有写指令记录下来&#xff08;读操作不记录&#xff09;。AOF文件是一个只追加的文件&…

Redis 高级数据结构业务实践

0、前言 本文所有代码可见 > 【gitee code demo】 本文会涉及 hyperloglog 、GEO、bitmap、布隆过滤器的介绍和业务实践 1、HyperLogLog 1.1、功能 基数统计&#xff08;去重&#xff09; 1.2、redis api 命令作用案例PFADD key element [element ...]添加元素到keyPF…

PortSip测试

安装PBX 下载 免费下载 PortSIP PBX 安装PBX&#xff0c;安装后&#xff0c;运行 &#xff0c;默认用户是admin 密码是admin&#xff0c;然后配置IP 为192.168.0.189 设置域名为192.168.0.189 配置分机 添加分机&#xff0c;添加了10001、10002、9999 三个分机&#xff0c…

深度学习实验第T2周:彩色图片分类

>- **&#x1f368; 本文为[&#x1f517;365天深度学习训练营](https://mp.weixin.qq.com/s/0dvHCaOoFnW8SCp3JpzKxg) 中的学习记录博客** >- **&#x1f356; 原作者&#xff1a;[K同学啊](https://mtyjkh.blog.csdn.net/)** 目录 一、前言 目标 二、我的环境&#…