Codeforces Round #276 (Div. 1)D（greedy+dp）_html/css_WEB-ITnose

D. 幼稚園

テストごとの制限時間

2 秒

テストごとのメモリ制限

256 メガバイト

入力

標準入力

出力

標準出力

幼稚園では、子どもたちはグループに分けられています。教師は子供たちを一列に並べ、各子供たちを整数のカリスマ値に関連付けました。各子供は 1 つのグループに所属する必要があります。各グループは、行の連続する子の空ではないセグメントである必要があります。グループの社交性は、グループ内の 2 人の子供のカリスマ性の最大の差です (特に、グループが 1 人の子供で構成されている場合、その社交性はゼロに等しい)。

教師は、子供たちをそのようなグループにいくつかのグループに分けたいと考えています。グループの総合的な社交性が最大になる方法です。この値を見つけるのを手伝ってください。

入力

最初の行には整数 n が含まれていますか?行内の子の数 (1?≤?n?≤?106)。

2 行目には n 個の整数 ai? が含まれます。 i 番目の子供のカリスマ性 (?-?109?≤?ai?≤?109)。

出力

すべてのグループの可能な最大合計社交性を出力します。

サンプル テスト

入力

51 2 3 1 2

出力

入力

33 3 3

出力

最初のテスト サンプルでは、​​考えられる除算のバリエーションの 1 つが次のとおりです: 最初の 3 人の子社会性 2 のグループを形成し、残りの 2 人の子供は社会性 1 のグループを形成します。

2 番目のテスト サンプルでは、​​どの除算も同じ結果になり、各グループの社会性は 0 になります。

問題点: 数を出し、いくつかの連続するセクションに分割することを要求し、各セクションの値はそのセクションの最大値と最小値の差であり、最後にすべてのセクションの最大値と

思路：写这个题解前先吐槽一下自己，自从域赛回来後多忙諸事，好久没刷题了，就拿这道不怎么难的题来说，想了好久

最後是見别人代才能書出来又是弱成狗，想每天安静静的做题都不行，生活就是这样啊，何時才成达自己的目标履行自己的诺言，好了，槽点完了，下面是题解

最初に注意、划分的区间一定捕调性、これは一种贪心思想、然后是dp了

dp[i] 表示前 i 数の最優值

如果a[i-2]a[i] dp[i]=max(dp[i-2]+a[i-1]-a[i], dp[i-1])

結果a[i-2]>a[i-1]>a[i] dp[i]=dp[i-1]+a[i-1] -a[i]

还有其它几种情况类似~