当前位置: 首页 > news >正文

C语言-算法-线性dp

[USACO1.5] [IOI1994]数字三角形 Number Triangles

题目描述

观察下面的数字金字塔。

写一个程序来查找从最高点到底部任意处结束的路径,使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。

在上面的样例中,从 7 → 3 → 8 → 7 → 5 7 \to 3 \to 8 \to 7 \to 5 73875 的路径产生了最大权值。

输入格式

第一个行一个正整数 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 1r1000,所有输入在 [ 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 题目描述 观察下面的数字金字塔。 写一个程序来查找从最高点到底部任意处结束的路径&#xff0c;使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。 在上面的样例中&#xff0c;从 7 → 3 → 8 →…...

Pandas应用-股票分析实战

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

Database history tablesupgraded

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

Dify学习笔记-应用发布(四)

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

优化用户体验测试应用领域:提升产品质量与用户满意度

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

顶顶通呼叫中心中间件机器人压力测试配置(mod_cti基于FreeSWITCH)

介绍 顶顶通呼叫中心中间件机器人压力测试(mod_cit基于FreeSWITCH) 一、配置acl.conf 打开ccadmin-》点击配置文件-》点击acl.conf-》我这里是已经配置好了的&#xff0c;这里的192.168.31.145是我自己的内网IP&#xff0c;你们还需要自行修改 二、配置线路 打开ccadmin-&g…...

Debezium发布历史87

原文地址&#xff1a; https://debezium.io/blog/2020/03/19/integration-testing-for-change-data-capture-with-testcontainers/ 欢迎关注留言&#xff0c;我是收集整理小能手&#xff0c;工具翻译&#xff0c;仅供参考&#xff0c;笔芯笔芯. 使用 Testcontainer 进行变更数…...

Leetcode131.分割回文串-Palindrome Patitioning-Python-回溯法

解题思路&#xff1a; 1.切割回文串&#xff0c;可以用解决找组合问题的思路解决&#xff0c;而解决组合问题&#xff0c;可以用回溯法&#xff0c;故本题选择回溯法。 2.理解两个事情&#xff1a;1.递归函数里的for循环是横向遍历给定字符串s的每一个字母。2.针对s的每一个字…...

Java面试——基础篇

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

C++——结构体

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

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. 全局变量定义在头文件中有什么问题&#xff1f; 2.6. 内存对齐 2.7. 什么是内存泄露 …...

VR数字展厅,平面静态跨越到3D立体化时代

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

Linux中LVM实验

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

外包干了一个月,技术退步明显。。。。。

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

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 (用户数据报协议) 应用层: 都是基于传输层协议的端口&#xff0c;总共端口0~65535 …...

Mac使用adb调试安卓手机

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

Web 开发 1: Flask 框架介绍和使用

在 Web 开发中&#xff0c;Flask 是一个流行且灵活的 Python Web 框架&#xff0c;用于构建 Web 应用程序。它简洁而易于上手&#xff0c;适用于小型到中型的项目。在本篇博客中&#xff0c;我将为你介绍 Flask 框架的基础知识和常用技巧&#xff0c;帮助你更好地掌握 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(" **** ***************** ** …...

Python|GIF 解析与构建(5):手搓截屏和帧率控制

目录 Python&#xff5c;GIF 解析与构建&#xff08;5&#xff09;&#xff1a;手搓截屏和帧率控制 一、引言 二、技术实现&#xff1a;手搓截屏模块 2.1 核心原理 2.2 代码解析&#xff1a;ScreenshotData类 2.2.1 截图函数&#xff1a;capture_screen 三、技术实现&…...

Linux 文件类型,目录与路径,文件与目录管理

文件类型 后面的字符表示文件类型标志 普通文件&#xff1a;-&#xff08;纯文本文件&#xff0c;二进制文件&#xff0c;数据格式文件&#xff09; 如文本文件、图片、程序文件等。 目录文件&#xff1a;d&#xff08;directory&#xff09; 用来存放其他文件或子目录。 设备…...

QMC5883L的驱动

简介 本篇文章的代码已经上传到了github上面&#xff0c;开源代码 作为一个电子罗盘模块&#xff0c;我们可以通过I2C从中获取偏航角yaw&#xff0c;相对于六轴陀螺仪的yaw&#xff0c;qmc5883l几乎不会零飘并且成本较低。 参考资料 QMC5883L磁场传感器驱动 QMC5883L磁力计…...

使用分级同态加密防御梯度泄漏

抽象 联邦学习 &#xff08;FL&#xff09; 支持跨分布式客户端进行协作模型训练&#xff0c;而无需共享原始数据&#xff0c;这使其成为在互联和自动驾驶汽车 &#xff08;CAV&#xff09; 等领域保护隐私的机器学习的一种很有前途的方法。然而&#xff0c;最近的研究表明&…...

Python爬虫实战:研究feedparser库相关技术

1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...

ESP32读取DHT11温湿度数据

芯片&#xff1a;ESP32 环境&#xff1a;Arduino 一、安装DHT11传感器库 红框的库&#xff0c;别安装错了 二、代码 注意&#xff0c;DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...

江苏艾立泰跨国资源接力:废料变黄金的绿色供应链革命

在华东塑料包装行业面临限塑令深度调整的背景下&#xff0c;江苏艾立泰以一场跨国资源接力的创新实践&#xff0c;重新定义了绿色供应链的边界。 跨国回收网络&#xff1a;废料变黄金的全球棋局 艾立泰在欧洲、东南亚建立再生塑料回收点&#xff0c;将海外废弃包装箱通过标准…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)

宇树机器人多姿态起立控制强化学习框架论文解析 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架&#xff08;一&#xff09; 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...

HTML前端开发:JavaScript 常用事件详解

作为前端开发的核心&#xff0c;JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例&#xff1a; 1. onclick - 点击事件 当元素被单击时触发&#xff08;左键点击&#xff09; button.onclick function() {alert("按钮被点击了&#xff01;&…...

(转)什么是DockerCompose?它有什么作用?

一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用&#xff0c;而无需手动一个个创建和运行容器。 Compose文件是一个文本文件&#xff0c;通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...