Pokémon Army (easy version) CodeForces

题意：

给你一个长度为n个序列v，你需要从中找一个子序列。这个子序列的值等于：子序列中奇数下标的值-偶数下标的值

你需要使得这个值尽可能大，让你输出这个最大值

题解：

dp[i][0]表示：在原序列从1到i位置中找一个子序列，这个子序列长度为偶数的子序列最大值

dp[i][1]表示：在原序列从1到i位置中找一个子序列，这个子序列长度为奇数的子序列最大值

初始化：

dp[i][0]=0

dp[i][1]=v[i]

转移方程：

1、dp[i][0]=max(dp[i-1][1]-v[i],dp[i-1][0]);

它的值或着是继承上一个dp[i-1][0]，或者是由之前的奇数长度再加上vi构成一个偶数长度序列dp[i-1][1]-vi

dp[i][1]=max(dp[i][1],max(dp[i-1][0]+v[i],dp[i-1][1]));

它的值可以由本身得到（因为它可以不取之前的序列，它自己就能构成一个长度为1的子序列），或者是继承上一个dp[i-1][1]，或者是由之前的偶数长度再加上vi构成一个奇数长度序列dp[i-1][0]+vi

代码：

#include<stdio.h>

#include<algorithm>

#include<iostream>

#include<string.h>

#include<math.h>

using namespace std;

typedef long long ll;

const int INF=0x3f3f3f3f;

const int maxn=3e5+10;

ll v[maxn],q[maxn][2];

int main()

{

    ll t;

    scanf("%lld",&t);

    while(t--)

    {

        ll n,m;

        scanf("%lld%lld",&n,&m);

        ll maxx=0;

        for(ll i=1;i<=n;++i)

        {

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

            v[i]=q[i][1];

            q[i][0]=0;

        }

        //printf("%lld %lld\n",q[1][0],q[1][1]);

        for(ll i=2;i<=n;++i)

        {

            q[i][0]=max(q[i-1][1]-v[i],q[i-1][0]);   //1 3 2

            q[i][1]=max(q[i][1],max(q[i-1][0]+v[i],q[i-1][1]));

            //printf("%lld %lld\n",q[i-1][0],q[i-1][1]);

        }

        printf("%lld\n",max(q[n][1],q[n][0]));

    }

    return 0;

}

巴特西

Pokémon Army (easy version) CodeForces - 1420C1 dp

最新文章

热门文章