[牛客小白月赛53]D.Breezing（DP）

题目链接：D-Breezing_牛客小白月赛53 (nowcoder.com)

题目 / Problem

给定一个序列B，让我们生成一个序列A，要求Ai∈[1, Bi]，且使得从∑[2, N] abs(a[i] - a[i - 1])最大。求出这个最大值。

思路 / Thought

显然这里应该的Ai要么取1，要么取Bi，因为这两种方案总是比取中间的一样或者更好。

如果按照朴素的想法可能进行dfs，也就是说每个位置，也就是每一层有两种选择，1或者Bi，但是这样时间复杂度就达到了O(2^N)十分惊人。

于是考虑到“大部分的序列中的dfs都可以由DP代替”，于是考虑用dp来解决这道题。

第一步确定dp状态。这里每个状态由两个值决定：位置和数字。

而数字只有两种选择：“最小值1”或者“最大值Bi”。

于是我们用dp[pos][0/1]来表示所有状态，其中第二维中0表示这一位数字是1,而1表示数字是Bi。

再想一下状态转移方程，dp[i][0]可以由dp[i-1][0]和dp[i-1][1]转移过来，dp[i][1]也一样，只需要取个大的就可以了，非常简单。

代码 / Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e5 + 9;
int dp[maxn][2];

inline int getabs(int x){return x < 0 ? -x : x;}

signed main()
{
    ios::sync_with_stdio(0);
    int N;cin >> N;
    vector<int> b(N + 1);
    for(int i = 1;i <= N; ++ i)cin >> b[i];
    
    for(int i = 2;i <= N; ++ i)
    {
        dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + b[i - 1] - 1);
        dp[i][1] = max(dp[i - 1][1] + getabs(b[i - 1] - b[i]), dp[i - 1][0] + b[i] - 1);
    }
    
    cout << max(dp[N][0], dp[N][1]) << '\n';
    
    return 0;
}