首页 > 其他分享 >洛谷题单指南-动态规划1-P1216 [USACO1.5] [IOI1994]数字三角形 Number Triangles

洛谷题单指南-动态规划1-P1216 [USACO1.5] [IOI1994]数字三角形 Number Triangles

时间:2024-04-18 09:33:05浏览次数:25  
标签:数字 USACO1.5 int 洛谷题 Number P1216 三角形 dp

原题链接:https://www.luogu.com.cn/problem/P1216

题意解读:计算数字三角形最高点到最后一行路径之和最大值,典型线性DP。

解题思路:

设a[i][j]表示数字三角形的值,

设dp[i][j]表示从最高点到第i行第j列路径之和的最大值,

由于每一步可以走到左下方的点也可以到达右下方的点,

所以dp[i][j] = dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]) + a[i][j],

如果数组下标从1开始,且默认值为0,则不用考虑数组边界和初始化问题。

100分代码:

#include <bits/stdc++.h>
using namespace std;

const int N = 1005;
int r, a[N][N], dp[N][N];
int ans;

int main()
{
    cin >> r;
    for(int i = 1; i <= r; i++)
        for(int j = 1; j <= i; j++)
            cin >> a[i][j];

    for(int i = 1; i <= r; i++)
        for(int j = 1; j <= i; j++)
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]) + a[i][j];

    for(int j = 1; j <= r; j++) ans = max(ans, dp[r][j]);
    cout << ans;
    return 0;
}

 

标签:数字,USACO1.5,int,洛谷题,Number,P1216,三角形,dp
From: https://www.cnblogs.com/jcwy/p/18142820

相关文章

  • AT_abc211_d [ABC211D] Number of Shortest paths 题解
    题目简述给定一张$n$个点$m$条边的无向无权图,问从$1$到$n$的最短路有多少条。题目分析设$cnt_i$表示从$1$到$i$的最短路条数,$dis_i$表示最短路。这道题可以考虑使用BFS做,对于一个点$v$,设第一次更新它的点为$u$,则它的转移应为$cnt_v\leftarrowcnt_u$并......
  • Mysql低版本中处理row_number()函数的适配问题
    在最近的项目中遇到了mysql8.0版本中row_number()函数在迁移数据库低版本mysql5.0版本无法使用的问题。具体sql如下:1SELECTDATE(a.CRETIFICATE_DATE)ASNAME,COUNT(*)ASCOUNTFROM2(SELECTCERTIFICATE_DATE,ENABLED,CERTIFICATION_STATE,ROW_NUMBER()over(PARTIT......
  • 洛谷题单指南-数学基础问题-P1403 [AHOI2005] 约数研究
    原题链接:https://www.luogu.com.cn/problem/P1403题意解读:计算1~n每个数的约数个数之和。解题思路:1、数学方法1~n的约数范围也在1~n,要计算每个数的约数个数之和可以从约数出发,比如约数是x,那么在1~n中一共有n/x个数包含x这个约数x从1一直枚举到n,就可以得出每个约数是多少个......
  • 洛谷题单指南-数学基础问题-P3601 签到题
    原题链接:https://www.luogu.com.cn/problem/P3601题意解读:求l~r范围内所有qiandao(x)之和,qiandao(x)为小于等于x的数中,与x不互质的数的个数。注意取模。解题思路:欧拉函数定义:phi(x)=x*(1-1/p1)*(1-1/p2)*...*(1-1/pn),p1,p2...pn为x的所有质因子其中:phi(x)表示1~x中所......
  • 洛谷题单指南-数学基础问题-P2660 zzc 种田
    原题链接:https://www.luogu.com.cn/problem/P2660题意解读:对一个长方形,切割出最少数量的正方形,计算所有正方形的边长。解题思路:长方形长、宽为x,y先判断x,y哪个长,哪个短长的作为l,短的作为s先切出s*s的正方形,一共可以切出l/s个,累加周长ans+=l/s*s*4在对剩下的s*......
  • 洛谷题单指南-数学基础问题-P2651 添加括号III
    原题链接:https://www.luogu.com.cn/problem/P2651题意解读:计算能否在除法a1​/a2​/a3​/.../an​式子中加括号,将一部分数变成分子,使得除法结果是整数。解题思路:在a1​/a2​/a3​/.../an​中,无论怎么加括号,a1一定是分子,a2一定是分母,那么可以判断把a3...an都作为分子,是否能除尽......
  • 洛谷题单指南-数学基础问题-P1414 又是毕业季II
    原题链接:https://www.luogu.com.cn/problem/P1414题意解读:有n个数,从其中选k个数,k=1,2,3......n,使得这k个数的gcd最大。解题思路:如何求k个数的最大公约数呢?暴力法肯定不行。可以从1到n枚举这个最大公约数i,看是否有>=k个数的因数是i具体来说,用桶数组存放所有整数,a[x]表示x的......
  • 洛谷题单指南-数学基础问题-P1572 计算分数
    原题链接:https://www.luogu.com.cn/problem/P1572题意解读:计算分数+、-运算的结果。解题思路:根据题目要求,逐项计算并约分,则不会超int,问题就比较直接了定义a1/b1为前一项的分子分母,a2/b2为当前项的分子分母依次遍历字符串,处理出分子和分母,本题的关键其实是字符串的处理当读取......
  • 洛谷题单指南-数学基础问题-P4057 [Code+#1] 晨跑
    原题链接:https://www.luogu.com.cn/problem/P4057题意解读:给定三个数,计算其最小公倍数。解题思路:三个数a、b、clcm(a,b,c)=lcm(lcm(a,b),c)100分代码:#include<bits/stdc++.h>usingnamespacestd;typedeflonglongLL;LLa,b,c;LLgcd(LLa,LLb){i......
  • [题解]CF55D Beautiful Numbers
    CF55DBeautifulNumbers打出暴搜后有些茫然,不知道该怎么优化才好,看了题解才豁然开朗。简单说下暴搜的思路:参数有\(pos,limit,lcm,num\)。其中\(lcm\)表示到\(pos+1\)位,所有非\(0\)位的\(lcm\)是多少;\(num\)表示填到\(pos+1\)位的整个数是多少。然后在\(pos=0\)时判断\(lcm\)是......