CF484D Kindergarten
题目描述：
有一组数，你要把他分成若干连续段。每一段的值，定义为这一段 数中最大值与最小值的差。 求一种分法，使得这若干段的值的和最大。
数据范围：
\(N < 10^6\), \(a[i] < 10^9\)。
思路：
仔细手摸几组数据，你会发现，我们将原序列分好后，每一段肯定是一个递增或者递减序列，即最大值和最小值出现在队头和队尾。
这个证明也是比较显然的，因为如果有一个不单调的子段，我们把他分成几个具有单调性的段答案总和不会小。
所以考虑令 \(dp_i\) 表示枚举到了第 \(i\) 个数，分了若干段后和的最大值。可以推出 \(dp_i=\max(dp_j+\mid a_i-a_{j+1}\mid,dp_{j-1}+\mid a_i-a_j\mid)\)
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define mem(a) memset(a,0,sizeof(a))
#define set(a,b) memset(a,b,sizeof(a))
#define ls p<<1
#define rs p<<1|1
#define pb(x) push_back(x)
#define pt(x) putchar(x)
#define T int t;cin>>t;while(t--)
#define rand RAND
using namespace std;
char buf[1<<20],*p1,*p2;
#define gc()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
template<class Typ> Typ &re(Typ &x){char ch=gc(),sgn=0; x=0;for(;ch<'0'||ch>'9';ch=gc()) sgn|=ch=='-';for(;ch>='0'&&ch<='9';ch=gc()) x=x*10+(ch^48);return sgn&&(x=-x),x;}
template<class Typ> void wt(Typ x){if(x<0) putchar('-'),x=-x;if(x>9) wt(x/10);putchar(x%10^48);}
const int inf=0x3f3f3f3f3f;
const int maxn=1e6+5;
const int mod=1e9+7;
int seed = 19243;
unsigned rand(){return seed=(seed*48271ll)%2147483647;}
int n;
int a[maxn];
int dp[maxn];
signed main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
int pre=1;
for(int i=2;i<=n;i++){
dp[i]=max(dp[pre]+abs(a[i]-a[pre+1]),dp[pre-1]+abs(a[i]-a[pre]));
if((a[i]>=a[i-1]&&a[i]>=a[i+1])||(a[i]<=a[i-1]&&a[i]<=a[i+1]))
pre=i;
}
cout<<dp[n]<<endl;
return 0;
}