codeforces C. Functions again

　　题意：给定了一个公式，让你找到一对（l,r）,求解出公式给定的F值。

　　当时没有想到，我把(-1)^(i-l)看成(-1)^i，然后思路就完全错了。其实这道题是个简单的dp+最长连续子序列。

　　O(n)求最长连续子序列代码

    ll maxx=, sum=, now=;

    for (int i=; i<n; i++) {    //数列1-n

        sum+=dp1[i];

        maxx=max(maxx, sum);

        if (sum<)  sum=;

    }

　　其实我们可以发现，其实正负是交错的，那么我们只要用两个dp（正负相反）的数组来存，再求一次最长连续子序列就好了。

/*  gyt

       Live up to every day            */

#include <stdio.h>

#include <cstdio>

#include <cmath>

#include <iostream>

#include <algorithm>

#include <vector>

#include <stack>

#include <cstring>

#include <queue>

#include <set>

#include <string>

#include <map>

#include <time.h>

#define PI acos(-1)

using namespace std;

typedef long long ll;

typedef double db;

const int maxn = 1e5+;

const ll maxm = 1e7;

const int mod = ;

const int INF = <<;

const db eps = 1e-;

const ll Max=1e19;

ll a[maxn], dp1[maxn], dp2[maxn];

void solve() {

    int n;  scanf("%d", &n);

    for (int i=; i<=n; i++) {

        scanf("%lld", &a[i]);

    }

    memset(dp1, , sizeof(dp1));

    memset(dp2, , sizeof(dp2));

    int f=;

    for (int i=; i<=n-; i++) {

        dp1[i]=abs(a[i]-a[i+])*f;

        dp2[i]=abs(a[i]-a[i+])*(-f);

        f = -f;

    }

    ll maxx=, sum=, now=;

    for (int i=; i<n; i++) {

        sum+=dp1[i];

        maxx=max(maxx, sum);

        if (sum<)  sum=;

    }

    sum=;

    for (int i=; i<n; i++) {

        sum+=dp2[i];

        maxx=max(maxx, sum);

        if (sum<)  sum=;

    }

    cout<<maxx<<endl;

}

int main() {

    int t=;

    //freopen("in.txt", "r", stdin);

    //scanf("%d", &t);

    for (int T=; T<=t; T++) {

        solve();

    }

}

巴特西

codeforces C. Functions again

最新文章

热门文章