首页 > 其他分享 >POJ--1163 The Triangle(DP)

POJ--1163 The Triangle(DP)

时间:2023-05-15 10:56:34浏览次数:53  
标签:Triangle -- int program POJ result triangle include dp

记录
10:43 2023-5-15

http://poj.org/problem?id=1163

reference:《挑战程序设计竞赛(第2版)》第二章练习题索引 p135

Description

Figure 1 shows a number triangle. Write a program that calculates the highest sum of numbers passed on a route that starts at the top and ends somewhere on the base. Each step can go either diagonally down to the left or diagonally down to the right.

Input

Your program is to read from standard input. The first line contains one integer N: the number of rows in the triangle. The following N lines describe the data of the triangle. The number of rows in the triangle is > 1 but <= 100. The numbers in the triangle, all integers, are between 0 and 99..

Output

Your program is to write to standard output. The highest sum is written as an integer.

Sample Input

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

Sample Output

30

一鱼俩吃(和之前3176一样 0ms就是用的改进后的方法(dp数组再利用))

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
#define MAX_N 100
typedef long long ll;
typedef unsigned int uint;
const int INF = 0x3f3f3f3f;

int dp[MAX_N + 1];  //定义dp[i] = 到这个点的时候得到的最大的值
int N;
// dp[i] = max(dp[i-1], dp[i]) + a; a表示此时读入的值

int main() {
    scanf("%d", &N);
    int a = 0;
    int result = -INF;
    for(int i = 1; i <= N; i++) {
        for(int j = i; j >= 1; j--) {
            scanf("%d", &a);
            dp[j] = max(dp[j-1], dp[j]) + a;
            result = max(result, dp[j]);
        }
    }
    printf("%d\n", result);
}

标签:Triangle,--,int,program,POJ,result,triangle,include,dp
From: https://www.cnblogs.com/57one/p/17401204.html

相关文章

  • 导数最终章
    思考以前总是分不清,导数和导函数,首先明白什么是导数,导数描述某点的领域的变换\[\lim_{x->x_0}\frac{\Deltay}{\Deltax}=\lim\frac{f(x_0+\Deltax)-f(x_0)}{\Deltax}\]导函数,其实也相当于函数,只是由无数个导数组成的函数题型题型1对应求某点的值,一般就是......
  • Windows 11、Windows 10使用VS2022安装 .NET 4.0、.NET 4.5等低版本环境
    由于新版windows10、windows11自带.NETFramework4.8,而一些旧的代码,又需要.NET4.0、.NET4.5等低版本的运行环境。最新携带运行环境版本如下:.NETFramework系统要求-.NETFramework|MicrosoftLearn安装低版本运行环境方法:无需安装VS2019,在VisualStudio2022中编......
  • 3D打印机报错!! {"code":"key243","msg":"Move out of range: 20.852 29.68
    修改配置文件stepper_z的配置终点需要改下,看你热床允许的倾斜度,相对于归零点,负的,最大的值 ......
  • 概率潮流计算MATLAB程序,这程序采用Monte Carlo模拟方法和不同的近似贝叶斯计算方法。
    概率潮流计算MATLAB程序,这程序采用MonteCarlo模拟方法和不同的近似贝叶斯计算方法。其中,贝叶斯计算可以参考IEEETrans文章:ZuluagaC.D.,álvarezM.A.(2018)BayesianProbabilisticPowerFlowAnalysisUsingJacobianApproximateBayesianComputation,toappearatIEE......
  • mysql将一个表的数据导入到另一个表
     将一个表的数据插入到另外一个表中的几种情况如下:1.如果2张表的字段一致,并且希望插入全部数据,可以用这种方法:   INSERT INTO目标表SELECT*FROM来源表;   例如:insertintoinsertTestselect*frominsertTest2;2.如果只希望导入指定字段,可以用这种方法: ......
  • Exp7 网络欺诈防范
    一.实验信息课程名称:网络对抗技术实验序号:7实验名称:网络欺诈防范实验人:20201214罗云帆二.实验内容本实践的目标理解常用网络欺诈背后的原理,以提高防范意识,并提出具体防范方法。具体实践有:简单应用SET工具建立冒名网站(1分)ettercapDNSspoof(1分)结合应用两种技术,用DNS......
  • 考虑阶梯式碳交易机制与电制氢的综合能源系统热电优化#Matlab程序,matlab代码
    考虑阶梯式碳交易机制与电制氢的综合能源系统热电优化#Matlab程序,matlab代码#碳交易电制氢阶梯式碳交易综合能源系统热电优化#matlab程序,考虑阶梯式碳交易机制的电热综合能源系统优化调度研究,考虑综合能源系统参与碳交易市场,引入阶梯式碳交易机制引导IES控制碳排放。看下面的......
  • KubeSphere 社区双周报 | 开源之夏已启动 | 2023.04.28-05.11
    KubeSphere社区双周报主要整理展示新增的贡献者名单和证书、新增的讲师证书以及两周内提交过commit的贡献者,并对近期重要的PR进行解析,同时还包含了线上/线下活动和布道推广等一系列社区动态。本次双周报涵盖时间为:2023.04.28-2023.05.11。贡献者名单新晋KubeSphereCon......
  • Matlab代码#优化调度#计及电转气协同的含碳捕集与垃圾焚烧虚拟电厂优化调度
    Matlab代码#优化调度#计及电转气协同的含碳捕集与垃圾焚烧虚拟电厂优化调度#电转气协同、碳捕集、虚拟电厂优化调度#matlab程序,计及电转气协同的含碳捕集与垃圾焚烧虚拟电厂优化调度,看下面的图片是运行结果,程序不负责讲解,采用yalmip+cplex求解器求解。碳捕集,电转气,P2G,优化调度ID:......
  • 如何设计分布式缓存-浅谈
    最近在看极客兔兔大佬的七天用Go从零实现系列,其中有个分布式缓存geeCache,从设计的角度整理下自己的想法和思路。如何设计分布式缓存?设计一个分布式缓存系统,需要考虑资源控制、淘汰策略、并发、分布式节点通信等各个方面的问题。从上述方面考虑,我们需要实现的功能如下1、缓存功......