51nod 1270 – 数组的最大代价 [DP]

Link

传送门

Problem

数组A包含N个元素A1, A2……AN。数组B包含N个元素B1, B2……BN。并且数组A中的每一个元素Ai,都满足1 <= Ai <= Bi。数组A的代价定义如下:
(公式表示所有两个相邻元素的差的绝对值之和)
给出数组B,计算可能的最大代价S。

Analysis

根据题意,A数组每个数都在1-Bi之间,然后我们再确定每个数。

可以用反证法发现,每个数要么为1,要么为Bi,只有这样,才能保证这个数跟相邻数的差值最大。问题转化成动态规划递推。

dp[i][0]表示第i个位置取0时能够达到的最大值,dp[i][1]表示第i个位置取B[i]时能够达到的最大值。并且有递推方程:dp[i][1] = max(dp[i-1][1] + abs(B[i]-B[i-1]), dp[i-1][0] + abs(B[i]-1)); dp[i][0] = max(dp[i-1][1] + abs(1 – B[i-1]), dp[i-1][0] + 0);

Code

#include <bits/stdc++.h>
using namespace std;

const int maxn = 51200;
int n, v[maxn], dp[maxn][2];

int main()
{
    cin >> n;
    for(int i = 1; i <= n; ++i)
        cin >> v[i];
    for(int i = 2; i <= n; ++i) {
        dp[i][1] = max(dp[i-1][1] + abs(v[i]-v[i-1]), dp[i-1][0] + abs(v[i]-1));
        dp[i][0] = max(dp[i-1][1] + abs(1 - v[i-1]), dp[i-1][0] + 0);
    }
    cout << max(dp[n][0], dp[n][1]) << endl;
    return 0;
}

欢迎留言