首页 > 代码库 > Codeforces 484(#276 Div 1) D Kindergarten DP
Codeforces 484(#276 Div 1) D Kindergarten DP
题意：给你一个数组，让你把连续的数分为一组，每一组的值为这一组数中的极差，问你这个怎样分组才能使得数组的极差和最大
解题思路：
可以分成 4种情况讨论
dp[i] 表示前 i+1项能得到的最大值
状态 状态转移方程
a[i-1] < a[i] < a[i+1] dp[i] = dp[i-1] + a[i+1] - a[i]
a[i-1] > a[i] < a[i+1] dp[i] = max(dp[i-1],dp[i-2] + a[i+1] -a[i])
a[i-1] > a[i] > a[i+1] dp[i] = dp[i-1] - a[i+1] + a[i]
a[i-1] < a[i] > a[i+1] dp[i] = max(dp[i-1],dp[i-2] - a[i+1] +a[i])
dp[n-1] 就是我们所求
解题代码：
1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 5 using namespace std; 6 7 typedef long long ll; 8 9 const int maxn=1000010;10 11 ll dp[maxn];12 int a[maxn];13 14 int main()15 {16 int n;scanf("%d",&n);17 for (int i=1;i<=n;i++) scanf("%d",&a[i]);18 dp[0]=0;19 for (int i=1;i<n;i++)20 if (a[i+1]>=a[i])21 {22 if ((i==1)||(a[i]>=a[i-1])) dp[i]=dp[i-1]+a[i+1]-a[i]; else dp[i]=max(dp[i-1],dp[i-2]+a[i+1]-a[i]);23 }24 else25 {26 if ((i==1)||(a[i]<a[i-1])) dp[i]=dp[i-1]-a[i+1]+a[i]; else dp[i]=max(dp[i-1],dp[i-2]-a[i+1]+a[i]);27 }28 cout<<dp[n-1]<<endl;29 return 0;30 }
from SanSiroWaltz
Codeforces 484(#276 Div 1) D Kindergarten DP
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。