[原创]codeforces 484D Kindergarten 【动态规划】

2017-01-11 22:32:31 Tabris_ 阅读数：288

博客爬取于2020-06-14 22:42:17
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/54350683

题目连接：http://codeforces.com/contest/484/problem/D

----------------------------------------------------------------------------.
D. Kindergarten
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard 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)(1 ≤ n ≤ 10^6).

The second line contains n integers ai — the charisma of the i-th child(−109≤ai≤109)( - 10^9 ≤ a_i ≤ 10^9).

Output
Print the maximum possible total sociability of all groups.

Examples
input
5
1 2 3 1 2
output
3
input
3
3 3 3
output
0
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的序列,然后让你将其分成任意段,每段的贡献是这段区间的最大值减最小值的差.求最终结果最大为多少.

解题思路:
通过对序列的分析我们能够知道，对于每一个单调的部分段 如果我们将其拆开了的话 其对结果的贡献就会变小，比如{1，2，3，4，5}对结果的贡献事4（5-1），如果拆开两段那么结果最多也就只能为3了，所以每一段区间我们都选取单调的。

然后对于整个数组，其结果事波动的，那么对于每两段区间会有一个相交的值,也就是拐点，我们只要在计算的时候要考虑其在左右区间哪一个对结果的贡献大我们就要怎么分就好了。

计算的时候采用dp的想法
dp[i] 表示以i结尾的结果最大值.
我们可以通过遍历找到最接近i的拐点位置,那么计算的时候判断这个拐点是在哪一个区间对结果的贡献大就好了…

dp[i]=max(dp[pre-1]+abs(a[i]-a[pre]),dp[pre]+abs(a[i]-a[pre+1]));

我这种dp废 ,不看题解基本都没想过dp,还在考虑单调队列,

附本题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# include <bits/stdc++.h>

using namespace std;

# define abs(x) ((x>=0)?(x):-(x))

typedef long long int LL;

const int N = 1e6+7;
/*******************************************/
LL a[N],dp[N];

int main(){
    int n;
    scanf("%d",&n);
    dp[0]=0ll;
    for(int i=1;i<=n;i++){
        scanf("%I64d",&a[i]);
        dp[i]=0ll;
    }
    int pre = 1;
    for(int i=2;i<=n;i++){
        dp[i]=max(dp[pre-1]+abs(a[i]-a[pre]),dp[pre]+abs(a[i]-a[pre+1]));
        if(a[i-1]<=a[i] && a[i]>=a[i+1]) pre=i;
        if(a[i-1]>=a[i] && a[i]<=a[i+1]) pre=i;
    }
    printf("%I64d\n",dp[n]);
    return 0;
}