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