首页 > 代码库 > 51Nod-1270-数组的最大代价
51Nod-1270-数组的最大代价
51Nod-1270-数组的最大代价
1270 数组的最大代价
数组A包含N个元素A1, A2......AN。数组B包含N个元素B1, B2......BN。并且数组A中的每一个元素Ai，都满足1 <= Ai <= Bi。数组A的代价定义如下：
（公式表示所有两个相邻元素的差的绝对值之和）
给出数组B，计算可能的最大代价S。
Input
第1行：1个数N，表示数组的长度(1 <= N <= 50000)。 第2 - N+1行：每行1个数，对应数组元素Bi(1 <= Bi <= 10000)。
Output
输出最大代价S。
Input示例
5 10 1 10 1 10
Output示例
36
题解：
对于数组中的一个数， 无非就有两种选择：（1）它本身，（2），1， 所以明显的简易DP问题
构建
动态规划公式： f[i][0] 表示第i个数由他本身表示， f[i][1] 表示第i个数有1表示。
就有公式：
dp[i][0] = max(dp[i-1][0]+abs(num[i]-num[i-1]), dp[i-1][1]+abs(num[i]-1));
dp[i][1] = max(dp[i-1][0]+abs(1-num[i-1]), dp[i-1][1]);
简易的DP方程
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
using namespace std;
const int MAXN = 50000;
int num[MAXN], dp[MAXN][2];
int func(int n){
dp[0][0] = dp[0][1] = 0;
for(int i=1; i<n; ++i){
dp[i][0] = max(dp[i-1][0]+abs(num[i]-num[i-1]), dp[i-1][1]+abs(num[i]-1));
dp[i][1] = max(dp[i-1][0]+abs(1-num[i-1]), dp[i-1][1]);
}
return max(dp[n-1][0], dp[n-1][1]);
}
int main(){
freopen("in.txt", "r", stdin);
int n;
while(scanf("%d", &n) != EOF){
for(int i=0; i<n; ++i){
scanf("%d", &num[i]);
}
int ans = func(n);
printf("%d\n", ans );
}
}
51Nod-1270-数组的最大代价
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。