本文主要是介绍Codeforces Round #276 (Div. 1) D. Kindergarten，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意是将一段序列分割成几段，使得这几段的极差和最大。
首先，我们可以发现，最终的被分出来的序列都应该是单调的，如果你是形如 4 6 1 的，很可能可以将4或者1分割出去得到更大的值
上述的情况下，在一定程度上让一段序列的元素少，这样构成的序列更多，获得的值也就可能越大
a[i-1] < a[i] < a[i+1] dp[i] = dp[i-1] + a[i+1] - a[i]
a[i-1] > a[i] < a[i+1] dp[i] = max(dp[i-1],dp[i-2] + a[i+1] -a[i])
a[i-1] > a[i] > a[i+1] dp[i] = dp[i-1] - a[i+1] + a[i]
a[i-1] < a[i] > a[i+1] dp[i] = max(dp[i-1],dp[i-2] - a[i+1] +a[i])
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>
#define CLR(x,y) memset(x,y,sizeof(x))
#define mp(x,y) make_pair(x,y)
#define eps 1e-9
#define INF 0x3f3f3f3f
#define LLINF 1LL<<62using namespace std;typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef complex<ld> point;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;template<class T>
inline bool read(T &n)
{T x = 0, tmp = 1;char c = getchar();while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();if(c == EOF) return false;if(c == '-') c = getchar(), tmp = -1;while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();n = x*tmp;return true;
}
template <class T>
inline void write(T n)
{if(n < 0){putchar('-');n = -n;}int len = 0,data[20];while(n){data[len++] = n%10;n /= 10;}if(!len) data[len++] = 0;while(len--) putchar(data[len]+48);
}
//-----------------------------------const int maxn=1000010;ll dp[maxn];
int a[maxn];int main()
{int n;read(n);for (int i=1; i<=n; i++)read(a[i]);dp[0]=0;for (int i=1; i<n; i++)if (a[i+1]>=a[i]){if ((i==1)||(a[i]>=a[i-1]))dp[i]=dp[i-1]+a[i+1]-a[i];elsedp[i]=max(dp[i-1],dp[i-2]+a[i+1]-a[i]);}else{if ((i==1)||(a[i]<a[i-1]))dp[i]=dp[i-1]-a[i+1]+a[i];elsedp[i]=max(dp[i-1],dp[i-2]-a[i+1]+a[i]);}write(dp[n-1]),putchar('\n');return 0;
}
在CF上还看到了一种神奇的做法，转移方程是一样的
nw相当于上面的dp[ i ]
mi维护的是递减区间，ma维护的是递增区间的dp值（我是这么理解的...
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define sqr(x) ((x)*(x))
#define lowbit(x) ((x)&-(x))
#define fill(A,B) memset(A,B,sizeof(A))
#define Copy(A,B) memcpy(A,B,sizeof(A))
#define rep(i,A,B) for(int i=A;i<=B;i++)
#define dep(i,B,A) for(int i=B;i>=A;i--)
#define RE(B,A) for(A::iterator it=B.begin();it!=B.end();++it)
#define re(i,A) for(int i=0;i<(int)A;i++)
#define re1(i,A) for(int i=1;i<(int)A;i++)
#define de(i,A) for(int i=A-1;i+1;i--)
#define For(i,A,B) for(int i=A;i<B;i++)
#define foredg(i,A) for(int i=H[A];i;i=e[i].nxt)
#define inf (1e9)
#define inf64 (1LL<<62)
#define mn 20011
#define Mod (10007)
#define eps (1e-5)
#define si(x) ((int)x.size())
#define MAX(A,B) A=max(A,B)
#define MIN(A,B) A=min(A,B)
#define ls (cur<<1)
#define rs (cur<<1|1)
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,int> pii;
typedef set<pair<pii,int> > Set;
const int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
int powmod(int a,int b){int tmp=1;a%=Mod;for(;b;b>>=1){if(b&1)tmp=(ll)tmp*a%Mod;a=(ll)a*a%Mod;}return tmp;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
template<class T>inline void R(T &xx){xx=0;char ch=getchar();bool F=0;while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();if(ch=='-')F=1,ch=getchar();while(ch>='0'&&ch<='9')xx=xx+xx+(xx<<3)+ch-48,ch=getchar();if(F)xx=-xx;}
template<class T>inline void add(int&x,T y){for(x+=y;x>=Mod;x-=Mod);}int n,x;ll ma,mi,nw;
int main(){
#ifndef ONLINE_JUDGE//freopen("1.in","r",stdin);//freopen("2.out","w",stdout);
#endifR(n);R(x);/*x=abs(x);*/ma=x,mi=-x;re1(i,n){R(x);MAX(mi,nw-x);MAX(ma,nw+x);MAX(nw,mi+x);MAX(nw,ma-x);}printf("%I64d\n",nw);return 0;
}这篇关于Codeforces Round #276 (Div. 1) D. Kindergarten的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
