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

- 日理万妓 2023-06-01 08:50 21阅读 0赞

1 #include <bits/stdc++.h>
     2 #define _for(i,a,b) for(int i = (a);i < b;i ++)
     3 typedef long long ll;
     4 using namespace std;
     5 int rnt = 0;
     6 int N;
     7 inline ll read()
     8 {
     9     ll ans = 0;
    10     char ch = getchar(), last = ' ';
    11     while(!isdigit(ch)) last = ch, ch = getchar();
    12     while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
    13     if(last == '-') ans = -ans;
    14     return ans;
    15 }
    16 inline void write(ll x)
    17 {
    18     if(x < 0) x = -x, putchar('-');
    19     if(x >= 10) write(x / 10);
    20     putchar(x % 10 + '0');
    21 }
    22 
    23 int main()
    24 {
    25     N = read();
    26     int dp[2][N];
    27     memset(dp,0,sizeof(dp));
    28     dp[0][0] = read();
    29     int rnt = 0;
    30     _for(i,1,N)
    31     {
    32         _for(j,0,i+1)
    33         {
    34             int tmp = read();
    35             if(j==0)
    36                 dp[i&0x1][j] = dp[!(i&0x1)][j] + tmp;
    37             else if(j==i)
    38                 dp[i&0x1][j] = dp[!(i&0x1)][j-1] + tmp;
    39             else
    40                 dp[i&0x1][j] = tmp + max(dp[!(i&0x1)][j],dp[!(i&0x1)][j-1]);
    41         }
    42     }
    43     
    44     _for(i,0,N)
    45         rnt = max(rnt,dp[!(N&0x1)][i]);
    46     write(rnt);
    47     return 0;
    48 }

转载于:https://www.cnblogs.com/Asurudo/p/11283426.html

发表评论取消回复

表情：

评论列表（有 0 条评论，21人围观）

还没有评论，来说两句吧...

相关阅读

相关 P3119-[USACO15JAN]草鉴定Grass Cownoisseur

1 include <iostream> 2 include <vector> 3 include <queue> 4 includ

怼烎@/ 2023年06月01日 08:57/ 0 赞/ 29 阅读

相关 P1216-[IOI1994][USACO1.5]数字三角形 Number Triangles

1 include <bits/stdc++.h> 2 define _for(i,a,b) for(int i = (a);i < b;i ++)

- 日理万妓/ 2023年06月01日 08:50/ 0 赞/ 22 阅读

相关 leetcode 611. Valid Triangle Number | 611. 有效三角形的个数（Java）

题目 [https://leetcode.com/problems/valid-triangle-number/][https_leetcode.com_problems

系统管理员/ 2023年01月24日 02:12/ 0 赞/ 26 阅读

相关数字三角形（洛谷P1216题题解，C++语言描述）

题目要求 [题目链接][Link 1] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_a

心已赠人/ 2022年11月07日 04:06/ 0 赞/ 212 阅读

相关 leetcode 611. Valid Triangle Number 构成三角形数量 + 双指针

Given an array consists of non-negative integers, your task is to count the number of tr

灰太狼/ 2022年06月03日 05:13/ 0 赞/ 162 阅读

相关洛谷P1118 [USACO06FEB]数字三角形Backward Digit Su…

题目描述 FJ and his cows enjoy playing a mental game. They write down the numbers from 1

朴灿烈づ我的快乐病毒、/ 2022年05月30日 02:09/ 0 赞/ 209 阅读

相关洛谷P1216 [USACO1.5]数字三角形 Number Triangles

题目描述观察下面的数字金字塔。写一个程序来查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。 7

你的名字/ 2022年05月28日 21:19/ 0 赞/ 186 阅读

相关洛谷P1216数字三角形

题目描述观察下面的数字金字塔。写一个程序来查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。 7

冷不防/ 2022年04月15日 05:05/ 0 赞/ 224 阅读

相关 A - Triangle（三角形+暴力）

题目链接： [http://codeforces.com/problemset/problem/18/A][http_codeforces.com_problemset_

拼搏现实的明天。/ 2022年02月18日 23:49/ 0 赞/ 201 阅读

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

题目描述观察下面的数字金字塔。写一个程序来查找从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以走到左下方的点也可以到达右下方的点。 7

待我称王封你为后i/ 2021年11月26日 07:31/ 0 赞/ 196 阅读