数据结构序列求权值

题意：

给定长度为n的序列，
现在要将他分成若干连续段，每段的权值为他的最大值减去最小值，
问最大权值和是多少

数据范围：n<=1e6

解法：

每一段都是单调的,否则可以通过拆分获得更大权值和
意思是每一段的两端一定是峰值点
例如1 2 3 1,权值为2 拆分为1 2和3 1,权值为1+2=3 那么对于峰值点,判断把他放在哪个段里更优即可

开一个变量last记录上一个峰值
显然转移有两种 1.d[last]+abs(a[i]-a[last+1]) 2.d[last-1]+abs(a[i]-a[last]) 第一种是不分在上一个段中作为峰值
第二种是分在上一个段中作为峰值 

code：

#include<bits/stdc++.h> using namespace std; #define int long long const int maxm=2e6+5; int d[maxm]; int a[maxm]; int n; int is(int i){ if(a[i]>=a[i-1]&&a[i]>=a[i+1])return 1; if(a[i]<=a[i-1]&&a[i]<=a[i+1])return 1; return 0; } signed main(){ ios::sync_with_stdio(0); cin>>n; for(int i=1;i<=n;i++)cin>>a[i]; int last=1;//上一个极值点 for(int i=2;i<=n;i++){ d[i]=max(d[last]+abs(a[i]-a[last+1]),d[last-1]+abs(a[i]-a[last])); if(is(i))last=i; } cout<<d[n]<<endl; return 0; } 

---

本文地址：https://blog.csdn.net/weixin_44178736/article/details/107724652