C语言-算法-线性dp
[USACO1.5] [IOI1994]数字三角形 Number Triangles
题目描述
观察下面的数字金字塔。
写一个程序来查找从最高点到底部任意处结束的路径,使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。
在上面的样例中,从 7 → 3 → 8 → 7 → 5 7 \to 3 \to 8 \to 7 \to 5 7→3→8→7→5 的路径产生了最大权值。
输入格式
第一个行一个正整数 r r r ,表示行的数目。
后面每行为这个数字金字塔特定行包含的整数。
输出格式
单独的一行,包含那个可能得到的最大的和。
样例 #1
样例输入 #1
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
样例输出 #1
30
提示
【数据范围】
对于 100 % 100\% 100% 的数据, 1 ≤ r ≤ 1000 1\le r \le 1000 1≤r≤1000,所有输入在 [ 0 , 100 ] [0,100] [0,100] 范围内。
代码
#include <stdio.h>
#include <stdlib.h>
int max(int a, int b); // 用于比较两个数的大小的函数
#define MAX 10000
int dp[MAX][MAX]; // 定义一个二维数组,用于存储金字塔和动态规划的状态int main(int argc, char *argv[])
{int r, i, j;scanf("%d", &r);for (i = 1; i <= r; i++){for (j = 1; j <=i; j++){scanf("%d", &dp[i][j]); // 读取该位置的值}}for (i = r - 1; i >= 1; i--) // 从倒数第二行开始,逐行向上{for (j = 1; j <= i; j++){// 选择下方或者右下方的较大值,然后加上当前位置的值dp[i][j] += max(dp[i + 1][j], dp[i + 1][j + 1]);}}printf("%d\n", dp[1][1]); // 输出顶部的值,即最大值return 0;
}int max(int a, int b) // 用于比较两个数的大小的函数
{if (a > b){return a;}else{return b;}
}
[USACO11JAN] Profits S
题目描述
The cows have opened a new business, and Farmer John wants to see how well they are doing. The business has been running for N (1 <= N <= 100,000) days, and every day i the cows recorded their net profit P_i (-1,000 <= P_i <= 1,000).
Farmer John wants to find the largest total profit that the cows have made during any consecutive time period. (Note that a consecutive time period can range in length from one day through N days.) Help him by writing a program to calculate the largest sum of consecutive profits.
奶牛们开始了新的生意,它们的主人约翰想知道它们到底能做得多好。这笔生意已经做了N(1≤N≤100,000)天,每天奶牛们都会记录下这一天的利润Pi(-1,000≤Pi≤1,000)。
约翰想要找到奶牛们在连续的时间期间所获得的最大的总利润。(注:连续时间的周期长度范围从第一天到第N天)。
请你写一个计算最大利润的程序来帮助他。
输入格式
* Line 1: A single integer: N
* Lines 2…N+1: Line i+1 contains a single integer: P_i
输出格式
* Line 1: A single integer representing the value of the maximum sum of profits for any consecutive time period.
样例 #1
样例输入 #1
7
-3
4
9
-2
-5
8
-3
样例输出 #1
14
提示
The maximum sum is obtained by taking the sum from the second through the sixth number (4, 9, -2, -5, 8) => 14.
代码
#include <stdio.h>
#include <stdlib.h>
int max(int a, int b); // 比较两个数的大小的函数
#define MAXN 200000int main(int argc, char *argv[])
{int N, i, P[MAXN], max_P;int dp[MAXN]; // 表示以第i天结束的最大连续子序列的和scanf("%d", &N);for (i = 1; i <= N; i++){scanf("%d", &P[i]); // 每天的利润}dp[1] = P[1]; // 初始化dp[1]为第一天的利润max_P = dp[1]; // 记录最大的利润for (i = 2; i <= N; i++){dp[i] = max(dp[i - 1] + P[i], P[i]); // 状态转移方程max_P = max(max_P, dp[i]); // 更新最大利润}printf("%d", max_P);return 0;
}int max(int a, int b) // 比较两个数的大小的函数
{if (a > b){return a;}else{return b;}
}
相关文章:

C语言-算法-线性dp
[USACO1.5] [IOI1994]数字三角形 Number Triangles 题目描述 观察下面的数字金字塔。 写一个程序来查找从最高点到底部任意处结束的路径,使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。 在上面的样例中,从 7 → 3 → 8 →…...

Pandas应用-股票分析实战
股票时间序列 时间序列: 金融领域最重要的数据类型之一 股价、汇率为常见的时间序列数据 趋势分析: 主要分析时间序列在某一方向上持续运动 在量化交易领域,我们通过统计手段对投资品的收益率进行时间序列建模,以此来预测未来的收…...

Database history tablesupgraded
zabbix升级到6之后,配置安装完成会有一个红色输出,但是不影响zabbix使用,出于强迫症,找到了该问题的解决方法。 Database history tables upgraded: No. Support for the old numeric type is deprecated. Please upgrade to nume…...

Dify学习笔记-应用发布(四)
1、发布为公开 Web 站点 使用 Dify 创建 AI 应用的一个好处在于,你可以在几分钟内就发布一个可供用户使用的 Web 应用,该应用将根据你的 Prompt 编排工作。 如果你使用的是自部署的开源版,该应用将运行在你的服务器上 如果你使用的是云服务&…...

优化用户体验测试应用领域:提升产品质量与用户满意度
在当今数字化时代,用户体验测试应用已经成为确保产品质量、提升用户满意度的关键工具。随着技术的不断发展,用户的期望也在不断演变,因此,为了保持竞争力,企业必须将用户体验置于产品开发的核心位置。本文将探讨用户体…...

顶顶通呼叫中心中间件机器人压力测试配置(mod_cti基于FreeSWITCH)
介绍 顶顶通呼叫中心中间件机器人压力测试(mod_cit基于FreeSWITCH) 一、配置acl.conf 打开ccadmin-》点击配置文件-》点击acl.conf-》我这里是已经配置好了的,这里的192.168.31.145是我自己的内网IP,你们还需要自行修改 二、配置线路 打开ccadmin-&g…...
Debezium发布历史87
原文地址: https://debezium.io/blog/2020/03/19/integration-testing-for-change-data-capture-with-testcontainers/ 欢迎关注留言,我是收集整理小能手,工具翻译,仅供参考,笔芯笔芯. 使用 Testcontainer 进行变更数…...
Leetcode131.分割回文串-Palindrome Patitioning-Python-回溯法
解题思路: 1.切割回文串,可以用解决找组合问题的思路解决,而解决组合问题,可以用回溯法,故本题选择回溯法。 2.理解两个事情:1.递归函数里的for循环是横向遍历给定字符串s的每一个字母。2.针对s的每一个字…...

Java面试——基础篇
目录 1、java语言有哪些优点和缺点? 2、JVM 、 JDK 和 JRE的关系 3、为什么说 Java 语言“编译与解释并存”? 4、Java和c的区别 5、基本数据类型 5.1、java的8种基本数据类型: 5.2、基本类型和包装类型的区别: 5.3、包装类型的缓存机…...

C++——结构体
1,结构体基本概念 结构体属于用户自定义的数据类型,允许用户存储不同的数据类型。像int(整型),浮点型,bool型,字符串型等都是属于系统内置的数据类型。而今天要学习的结构体则是属于我们自定义…...

C++技术要点总结, 面试必备, 收藏起来慢慢看
目录 1. 语言对比 1.1 C 11 新特性 2.2 C 和 C 的区别 2.3 Python 和 C 的区别 2. 编译内存相关 2.1. C 程序编译过程 2.2. C 内存管理 2.3. 栈和堆的区别 2.4. 变量的区别 2.5. 全局变量定义在头文件中有什么问题? 2.6. 内存对齐 2.7. 什么是内存泄露 …...

VR数字展厅,平面静态跨越到3D立体化时代
近些年,VR的概念被越来越多的人提起,较为常见的形式就是VR数字展厅。VR数字展厅的出现,让各地以及各行业的展厅展馆的呈现和宣传都发生了很大的改变和革新,同时也意味着展览传播的方式不再局限于原来的图文、视频,而是…...

Linux中LVM实验
LVM实验: 1、分区 -L是大小的意思-n名称的意思 从vg0(卷组)分出来 2、格式化LV逻辑卷 LVM扩容 如果icdir空间不够了, 扩展空间lvextend -L 5G /dev/vg0/lv1 /dev/vg0/lv1(pp,vg,lv) 刷新文件系统xfs_growfs /lvdir VG扩容 …...

外包干了一个月,技术退步明显。。。。。
先说一下自己的情况,本科生,19年通过校招进入南京某软件公司,干了接近4年的功能测试,今年年初,感觉自己不能够在这样下去了,长时间呆在一个舒适的环境会让一个人堕落!而我已经在一个企业干了四年的功能测试…...

gitlab.rb主要配置
根据是否docker安装,进入挂载目录或安装目录 修改此文件,我一般是在可视化窗口中修改,有时候也在命令行手敲 将下面的配置复制到该文件中 external_url http://192.168.100.50 # nginx[listen_port] = 8000 (docker安装的这一行不需要,因为端口映射导致此处修改会导致访问…...
网络协议基础
tcp/ip协议簇 TCP/IP协议族 网络接口层(没有特定的协议) 物理层 数据链路层 网络层: IP (v4/v6) ARP(地址解析协议) RARP . ICMP (Internet控制报文协议) IGMP 传输层: TCP (传输控制协议) UDP (用户数据报协议) 应用层: 都是基于传输层协议的端口,总共端口0~65535 …...

Mac使用adb调试安卓手机
0x00 背景 最近windows电脑休息,用mac办公比较多,手机用时间长了,不太灵光,准备修理一番。于是要用mac调试下android手机。配置略显麻烦,网上的步骤多参差不齐。估计是入门步骤,大佬们也懒得写的太细。于是…...

Web 开发 1: Flask 框架介绍和使用
在 Web 开发中,Flask 是一个流行且灵活的 Python Web 框架,用于构建 Web 应用程序。它简洁而易于上手,适用于小型到中型的项目。在本篇博客中,我将为你介绍 Flask 框架的基础知识和常用技巧,帮助你更好地掌握 Web 开发…...
Centos7.6之禅道开源版17.6.1安装记录
Centos7.6之禅道开源版17.6.1安装记录 文章目录 Centos7.6之禅道开源版17.6.1安装记录1. 下载2. 安装3. 登录4. 连接数据库1. 本地连接2. 远程连接1. 开启远程访问用户2. 更改mysql绑定的主机3. 重启Apache与MySQL服务 4. 常用命令1. Apache和Mysql常用命令2. 其他 1. 下载 官网…...
有趣的代码(简单)
1.代码1 #include<stdio.h> #include<string.h> #include<windows.h> #define _CRT_SECURE_NO_WARNINGS 1 void love() {system("color 4");printf(" **** ***************** ** …...

Chapter03-Authentication vulnerabilities
文章目录 1. 身份验证简介1.1 What is authentication1.2 difference between authentication and authorization1.3 身份验证机制失效的原因1.4 身份验证机制失效的影响 2. 基于登录功能的漏洞2.1 密码爆破2.2 用户名枚举2.3 有缺陷的暴力破解防护2.3.1 如果用户登录尝试失败次…...
设计模式和设计原则回顾
设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...
OpenLayers 分屏对比(地图联动)
注:当前使用的是 ol 5.3.0 版本,天地图使用的key请到天地图官网申请,并替换为自己的key 地图分屏对比在WebGIS开发中是很常见的功能,和卷帘图层不一样的是,分屏对比是在各个地图中添加相同或者不同的图层进行对比查看。…...

如何在网页里填写 PDF 表格?
有时候,你可能希望用户能在你的网站上填写 PDF 表单。然而,这件事并不简单,因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件,但原生并不支持编辑或填写它们。更糟的是,如果你想收集表单数据ÿ…...

论文笔记——相干体技术在裂缝预测中的应用研究
目录 相关地震知识补充地震数据的认识地震几何属性 相干体算法定义基本原理第一代相干体技术:基于互相关的相干体技术(Correlation)第二代相干体技术:基于相似的相干体技术(Semblance)基于多道相似的相干体…...

初探Service服务发现机制
1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能:服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源…...

莫兰迪高级灰总结计划简约商务通用PPT模版
莫兰迪高级灰总结计划简约商务通用PPT模版,莫兰迪调色板清新简约工作汇报PPT模版,莫兰迪时尚风极简设计PPT模版,大学生毕业论文答辩PPT模版,莫兰迪配色总结计划简约商务通用PPT模版,莫兰迪商务汇报PPT模版,…...

Qemu arm操作系统开发环境
使用qemu虚拟arm硬件比较合适。 步骤如下: 安装qemu apt install qemu-system安装aarch64-none-elf-gcc 需要手动下载,下载地址:https://developer.arm.com/-/media/Files/downloads/gnu/13.2.rel1/binrel/arm-gnu-toolchain-13.2.rel1-x…...

9-Oracle 23 ai Vector Search 特性 知识准备
很多小伙伴是不是参加了 免费认证课程(限时至2025/5/15) Oracle AI Vector Search 1Z0-184-25考试,都顺利拿到certified了没。 各行各业的AI 大模型的到来,传统的数据库中的SQL还能不能打,结构化和非结构的话数据如何和…...
人工智能 - 在Dify、Coze、n8n、FastGPT和RAGFlow之间做出技术选型
在Dify、Coze、n8n、FastGPT和RAGFlow之间做出技术选型。这些平台各有侧重,适用场景差异显著。下面我将从核心功能定位、典型应用场景、真实体验痛点、选型决策关键点进行拆解,并提供具体场景下的推荐方案。 一、核心功能定位速览 平台核心定位技术栈亮…...