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