CodeforcesRound#276(Div.1)D（贪心+dp）_html/css_WEB-ITnose
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了CodeforcesRound#276(Div.1)D（贪心+dp）_html/css_WEB-ITnose，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2501字，纯文字阅读大概需要4分钟。
内容图文
D. Kindergarten
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
In a kindergarten, the children are being divided into groups. The teacher put the children in a line and associated each child with his or her integer charisma value. Each child should go to exactly one group. Each group should be a nonempty segment of consecutive children of a line. A group's sociability is the maximum difference of charisma of two children in the group (in particular, if the group consists of one child, its sociability equals a zero).
The teacher wants to divide the children into some number of groups in such way that the total sociability of the groups is maximum. Help him find this value.
Input
The first line contains integer n ? the number of children in the line (1?≤?n?≤?106).
The second line contains n integers ai ? the charisma of the i-th child (?-?109?≤?ai?≤?109).
Output
Print the maximum possible total sociability of all groups.
Sample test(s)
input
51 2 3 1 2
output
input
33 3 3
output
Note
In the first test sample one of the possible variants of an division is following: the first three children form a group with sociability 2, and the two remaining children form a group with sociability 1.
In the second test sample any division leads to the same result, the sociability will be equal to 0 in each group.
题意：给出n个数，要求你把它分成若干个连续的区间，每个区间的权值定义为该区间最大值与最小值的差值，最后求所有区间的最大权值和
思路：写这个题解前先吐槽一下自己，自从区域赛回来以后忙各种杂事，好久没刷题了，就拿这道不怎么难的题来说，想了好久
最后还是看别人代码才写出来也是弱成狗，想每天安安静静的做题都不行，生活就是这样啊，何时才成达成自己的目标履行自己的诺言，好了，槽点吐完，下面是题解
首先注意到，划分的区间一定满足单调性，这是一种贪心思想，然后就是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]
还有其它几种情况类似~
内容总结
以上是互联网集市为您收集整理的CodeforcesRound#276(Div.1)D（贪心+dp）_html/css_WEB-ITnose全部内容，希望文章能够帮你解决CodeforcesRound#276(Div.1)D（贪心+dp）_html/css_WEB-ITnose所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。