[牛客小白月赛53]D.Breezing(DP)

发布于 2022-07-09  230 次阅读


题目链接: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;
}