当前位置: 首页 > 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(" **** ***************** ** …...

KubeSphere 容器平台高可用:环境搭建与可视化操作指南

Linux_k8s篇 欢迎来到Linux的世界&#xff0c;看笔记好好学多敲多打&#xff0c;每个人都是大神&#xff01; 题目&#xff1a;KubeSphere 容器平台高可用&#xff1a;环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...

vscode里如何用git

打开vs终端执行如下&#xff1a; 1 初始化 Git 仓库&#xff08;如果尚未初始化&#xff09; git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...

手游刚开服就被攻击怎么办?如何防御DDoS?

开服初期是手游最脆弱的阶段&#xff0c;极易成为DDoS攻击的目标。一旦遭遇攻击&#xff0c;可能导致服务器瘫痪、玩家流失&#xff0c;甚至造成巨大经济损失。本文为开发者提供一套简洁有效的应急与防御方案&#xff0c;帮助快速应对并构建长期防护体系。 一、遭遇攻击的紧急应…...

PHP和Node.js哪个更爽?

先说结论&#xff0c;rust完胜。 php&#xff1a;laravel&#xff0c;swoole&#xff0c;webman&#xff0c;最开始在苏宁的时候写了几年php&#xff0c;当时觉得php真的是世界上最好的语言&#xff0c;因为当初活在舒适圈里&#xff0c;不愿意跳出来&#xff0c;就好比当初活在…...

UDP(Echoserver)

网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法&#xff1a;netstat [选项] 功能&#xff1a;查看网络状态 常用选项&#xff1a; n 拒绝显示别名&#…...

pam_env.so模块配置解析

在PAM&#xff08;Pluggable Authentication Modules&#xff09;配置中&#xff0c; /etc/pam.d/su 文件相关配置含义如下&#xff1a; 配置解析 auth required pam_env.so1. 字段分解 字段值说明模块类型auth认证类模块&#xff0c;负责验证用户身份&am…...

多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验

一、多模态商品数据接口的技术架构 &#xff08;一&#xff09;多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如&#xff0c;当用户上传一张“蓝色连衣裙”的图片时&#xff0c;接口可自动提取图像中的颜色&#xff08;RGB值&…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个生活电费的缴纳和查询小程序

一、项目初始化与配置 1. 创建项目 ohpm init harmony/utility-payment-app 2. 配置权限 // module.json5 {"requestPermissions": [{"name": "ohos.permission.INTERNET"},{"name": "ohos.permission.GET_NETWORK_INFO"…...

[Java恶补day16] 238.除自身以外数组的乘积

给你一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O(n) 时间复杂度…...

根据万维钢·精英日课6的内容,使用AI(2025)可以参考以下方法:

根据万维钢精英日课6的内容&#xff0c;使用AI&#xff08;2025&#xff09;可以参考以下方法&#xff1a; 四个洞见 模型已经比人聪明&#xff1a;以ChatGPT o3为代表的AI非常强大&#xff0c;能运用高级理论解释道理、引用最新学术论文&#xff0c;生成对顶尖科学家都有用的…...