cf484D. Kindergarten

cf484D. Kindergarten

链接

点击跳转

题解

这题感觉就是要瞎分析一波然后莽

可以发现分成的每一段都是单调的

但是端点处不一定属于哪边，这个时候 d p dp dp一下就好了

代码

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define iinf 0x3f3f3f3f
#define linf (1ll<<60)
#define eps 1e-8
#define maxn 1000010
#define cl(x) memset(x,0,sizeof(x))
#define rep(_,__) for(_=1;_<=(__);_++)
#define em(x) emplace(x)
#define emb(x) emplace_back(x)
#define emf(x) emplace_front(x)
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
ll read(ll x=0)
{ll c, f(1);for(c=getchar();!isdigit(c);c=getchar())if(c=='-')f=-f;for(;isdigit(c);c=getchar())x=x*10+c-0x30;return f*x;
}
ll n, f[maxn], g[maxn][2], a[maxn];
int main()
{ll i, x;n=read();rep(i,n)a[i]=read();g[1][0]=g[1][1]=1;for(i=2;i<=n;i++){g[i][0]=g[i][1]=1;if(a[i]>=a[i-1])g[i][0]+=g[i-1][0];if(a[i]<=a[i-1])g[i][1]+=g[i-1][1];}for(i=2;i<=n;i++){ll t=g[i][g[i][1]>g[i][0]];f[i]=f[i-t]+max(a[i],a[i-t+1])-min(a[i],a[i-t+1]);f[i]=max(f[i],f[i-t+1]+max(a[i],a[i-t+2])-min(a[i],a[i-t+2]));}printf("%lld",f[n]);return 0;
}