codeforces 484D kindergarten

川长思鸟来 2022-08-14 00:49 45阅读 0赞

刚开始没细读题目，直接快排后减了了一下，就交了上去，结果直接Wa。猥琐的看了数据，竟然发现两组数据只是位置不同，得到的答案竟然也不相同，觉得不妙。

题目大意：

给你一列数，让你把他们分成几个区间，每个区间的代表值为区间中数的最大值减去最小值，求总的代表值之和最大为多少?

如果一列数，a\[i\]....a\[j\],是单调递增的的，则这一段的最大代表值为a\[j\]-a\[i\].并加到计算递增数列的变量值上；如果出现转折点则转到另一个变量值上\]，加起来计算递减段的的代表值之和。

用dp可很好解决。

代码如下：

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    const int maxn=1e6+5;
    int charisma[maxn];
    long long dp[maxn][2];
    
    int main(){
        int n;
        while(scanf("%d",&n)==1){
            scanf("%d",charisma);
            for(int i=1;i<n;i++){
                scanf("%d",charisma+i);
                if(charisma[i]>charisma[i-1]){
                    dp[i][0]=max(dp[i-1][1],dp[i-1][0]+charisma[i]-charisma[i-1]);
                    dp[i][1]=max(dp[i-1][0],dp[i-1][1]);
                }
                else{
                    dp[i][1]=max(dp[i-1][0],dp[i-1][1]+charisma[i-1]-charisma[i]);
                    dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
                }
        }
        printf("%I64d\n",max(dp[n-1][0],dp[n-1][1]));
        }
       return 0;
    }

发表评论取消回复

表情：

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

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

相关阅读

相关 CodeForces 55D

题意略。思路：本题可以说是醉翁之意不在酒了。要解开本题有几个关键点： 1.意识到数X = An An-1 An-2 An-3 .... A2 A1能被\{An,An-

深碍√TFBOYSˉ_/ 2023年08月17日 16:37/ 0 赞/ 173 阅读

相关 CodeForces1214D

[CodeForces1214D][] 这个题据我所知有两种比较优秀的做法. 第一种是\\(DP\\)统计每个点的路径数,然后找出必经点,再从必经点开始\\(bfs\\

柔光的暖阳◎/ 2023年06月02日 11:58/ 0 赞/ 74 阅读

相关 CodeForces1208D

CodeForces1208D 也是挺吓人的一道题,我一开始以为给的是每个数字前比它小的数字有几个,然后我就苦苦看不懂样例... 然后我冷静了一下,重新分析,读题,发现

浅浅的花香味﹌/ 2023年06月02日 11:56/ 0 赞/ 83 阅读

相关 codeforces 484D kindergarten

刚开始没细读题目，直接快排后减了了一下，就交了上去，结果直接Wa。猥琐的看了数据，竟然发现两组数据只是位置不同，得到的答案竟然也不相同，觉得不妙。题目大意：给你一列数，

川长思鸟来/ 2022年08月14日 00:49/ 0 赞/ 46 阅读

相关 codeforces D. Maximum Value

D. Maximum Value time limit per test 1 second memory limit per test 256 megabytes i

约定不等于承诺〃/ 2022年07月24日 09:16/ 0 赞/ 212 阅读

相关 codeforces 276D 贪心

D. Little Girl and Maximum XOR time limit per test 2 seconds memory limit per test 2

妖狐艹你老母/ 2022年07月24日 06:26/ 0 赞/ 211 阅读

相关 codeforces 519D dp

D. A and B and Interesting Substrings time limit per test 2 seconds memory limit per

雨点打透心脏的1/2处/ 2022年07月24日 05:08/ 0 赞/ 215 阅读

相关 Codeforces 496D

题意 -------------------- 进行若干场比赛，每次比赛两人对决，赢的人得到1分，输的人不得分，先得到t分的人获胜，开始下场比赛，某个人率先赢下s场比赛

你的名字/ 2022年07月16日 14:15/ 0 赞/ 168 阅读

相关 CodeForces - 1087D

CodeForces - 1087D https://vjudge.net/problem/2115151/origin 2\和/叶子结点的个数 includ

红太狼/ 2021年10月30日 01:36/ 0 赞/ 279 阅读

相关 [Codeforces]871D Paths

　　失踪OJ回归。　　毕竟这样的数论没做过几道，碰上一些具体的应用还是无所适从啊。小C还是借助这题大致摸索一下莫比乌斯函数吧。 Description 　　有

本是古典何须时尚/ 2021年09月29日 09:06/ 0 赞/ 354 阅读