贪心观察+DP决策。

首先需要观察到一个结论:分割后的每一段肯定是单调增或者单调减的。

然后可以根据dp来决策如何分割价值最多。

dp[i][0]表示放完第i个,最后一段是递减的情况下的最大价值

dp[i][1]表示放完第i个,最后一段是递增的情况下的最大价值

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std; const int maxn=1e6+;
long long dp[maxn][];
long long a[maxn];
int n; int main()
{
scanf("%d",&n);
a[]=; dp[][]=dp[][]=;
for(int i=;i<=n;i++) scanf("%lld",&a[i]);
for(int i=;i<=n;i++)
{
if(a[i]>a[i-])
{
dp[i][]=max(dp[i-][]+a[i]-a[i-],dp[i-][]);
dp[i][]=max(dp[i-][],dp[i-][]);
}
else if(a[i]<a[i-])
{
dp[i][]=max(dp[i-][]+a[i-]-a[i],dp[i-][]);
dp[i][]=max(dp[i-][],dp[i-][]);
}
else
{
dp[i][]=dp[i][]=max(dp[i-][],dp[i-][]);
}
}
printf("%lld\n",max(dp[n][],dp[n][]));
return ;
}

最新文章

  1. QuartZ Cron表达式
  2. 基于Ubuntu14.04系统的nvidia tesla K40驱动和cuda 7.5安装笔记
  3. Centos6下rpm安装MySQL5.6
  4. [Architect] Abp 框架原理解析(3) DynamicFilters
  5. javascript return false 详解
  6. 关键字 this 的作用
  7. 轻松学Linux之使用转义字符
  8. js中对arry数组的各种操作小结
  9. Mapreduce运行过程分析(基于Hadoop2.4)——(一)
  10. block中无法使用C数组变量
  11. #include &lt;boost/bind.hpp&gt;
  12. Form表单中的action路径问题
  13. JSTL(JSP Standard Tag Library ,JSP标准标签库)
  14. Log4j appender输出类型配置
  15. Alibaba(阿里) RocketMQ入门实例
  16. NET4.6下的UTC时间转换
  17. jQuery创建元素和添加子元素
  18. Java11实战:模块化的 Netty RPC 服务项目
  19. windows 下mysql 重设root密码方法
  20. WPF 未能加载文件或程序集“CefSharp.Core.dll”或它的某一个依赖项

热门文章

  1. 今天遇到了隐藏顶部菜单栏(top bar)的菜鸟问题,解决了。
  2. Qt多线程编程总结(一)
  3. centos mono
  4. rebar
  5. 如何获取path与basePath
  6. win10怎么启用网络发现,网络发现已关闭怎么办
  7. Ubuntu配置eclipse
  8. Setting DPDK+OVS+QEMU on CentOS
  9. Android中的对话框AlertDialog使用技巧合集-转载
  10. Java的动态加载及其安全性问题