Codeforces 789 C Functions again DP-白红宇

Codeforces 789 C Functions again DP

阅读量：6895 次

发布时间：2019-06-27

本文共 1082 字，大约阅读时间需要 3 分钟。

　　题目链接： http://codeforces.com/problemset/problem/789/C

　　题目描述：给定一个数列，问从某项开始加一项减一项的最大值是多少

　　解题思路：先把数列分成两种情况，一种是第一个正第二个负第三个正...... 一种是第一个负第二个正第三个负...... DP求一个连续子序列最大和就可以了

　　代码：

#include 
      
       #include 
       
        #include 
        #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               using namespace std;typedef long long ll;const ll maxn = 1e5+10;ll a[maxn];ll b[maxn];ll c[maxn];ll d[maxn];ll solve( ll * p, ll len ) { ll ans = 0; ll cnt = 0; for( ll i = 1; i <= len; i++ ) { cnt += p[i]; if( cnt < 0 ) cnt = 0; else { if( cnt > ans ) ans = cnt; } } return ans;}int main() { ll n; scanf( "%lld", &n ); for( ll i = 1; i <= n; i++ ) { scanf( "%lld", a+i ); } for( ll i = 1; i <= n-1; i++ ) { b[i] = abs(a[i+1]-a[i]); } n--; for( ll i = 1; i <= n; i++ ) { if( i & 1 ) { c[i] = -b[i]; d[i] = b[i]; } else { c[i] = b[i]; d[i] = -b[i]; } } printf( "%lld\n", max(solve(c,n), solve(d, n))); return 0;}