牛客小白赛53--Breezing

链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网

勇敢的牛牛得到了一个数列 B，他认为这个数列不够可爱，于是他决定重新创造一个数列 A，规则如下。

对于所有的 i，需要保证 Ai 在 [1,Bi] 这个区间内。

现在，我们称数列 A 的可爱值 k为「数列 A 中相邻两个数差的绝对值的和」，求最大的可爱值。

输入描述:

第一行，一个正整数 n(2≤n≤105)n(2 le nle 10^5)n(2≤n≤105)。

第二行，nnn 个正整数，表示数列 BBB 中的数，1≤Bi≤1041le B_i le 10^41≤Bi≤104。

输出描述:

一行，一个非负整数表示最大的可爱值 k。

示例1

输入

11 45 14 19 1 9 8 10

输出

149

示例2

输入

107 97 119 97 105 105

输出

550

题意：就是保证重新创建一个新的数组A，A数组的顺序与B数组一致，但对于A数组的第i个数要保证是[1 Bi]这个区间里的数，然后找到A数组的相邻两个数的最大差值的和。

思路：是一个典型的动态规划问题，因为是最大差值，那这个数不是1就是它本身，这样才能满足条件，因此就有两种情况啊dp[i][0](表示第i个数取1）和dp[i][1](表示第i个数取本身）

dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + abs(a[i] - 1))(当Ai取1时，求上一个也取1的差值与上一个取本身差值的最大值）
dp[i][1] = max(dp[i - 1][1] + abs(a[i + 1] - a[i]), dp[i - 1][0] + abs(a[i + 1] - 1))（党Ai取本身时，求上一个取1的差值与上一个也取本身的差值的最大值）

ac代码

#include
#include
#include
#include
#include
#include
#include
#include
#include 
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define ll long long
const ll inf = 0x3f3f3f3f3f3f3f3f;//表示无穷大
using namespace std;
//a&1==a%2==1(表示是奇数）
int a[200005];
int dp[200005][2];
int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n - 1; i++)
    {
        dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + abs(a[i] - 1));
        dp[i][1] = max(dp[i - 1][1] + abs(a[i + 1] - a[i]), dp[i - 1][0] + abs(a[i + 1] - 1));
    }
    cout << max(dp[n - 1][0], dp[n - 1][1]) << endl;
    return 0;
}

牛客小白赛53--Breezing

C/C++/C#相关栏目本月热门文章