openjudge 8464
这道题其实很简单,算是DP的基础题,比较适合开拓DP思维。
题目比较有欺骗性,其实稍微想想就可以解决,因为题意说第一次卖出后才能买入,所以我们可以考虑枚举断点,所以题目一下变得简单,我们线性扫两遍,算最大值就好了。
具体为:
由于不能同时进行两次交易,所以枚举断点,一遍扫做1到n的前n个的最大值,由于最大值一定是单调递增的,所以每次读入新的a[i],判断是否有更优解就好了,同理,一遍扫n到1的后n个的最大值,做同样的事,然后枚举断点取最大值。
代码如下:
#include<stdio.h>
int T,n,a[],f[],g[],ans;
int main()
{
scanf("%d",&T);
while(T--)
{
int best=-,temp=;
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%d",&a[i]);
for(int i=;i<=n;i++)
{
if(a[i]<temp)
temp=a[i];
if(a[i]-temp>best)
best=a[i]-temp;
f[i]=best;
}
best=-,temp=-;
for(int i=n;i>=;i--)
{
if(a[i]>temp)
temp=a[i];
if(temp-a[i]>best)
best=temp-a[i];
g[i]=best;
}
for(int i=;i<=n;i++)
if(f[i]+g[i]>ans)ans=f[i]+g[i];
printf("%d\n",ans);
ans=;
}
return ;
}
刷题向》DP》关于基础DP(easy)的更多相关文章
-
$2019$ 暑期刷题记录1:(算法竞赛DP练习)
$ 2019 $ 暑期刷题记录: $ POJ~1952~~BUY~LOW, BUY~LOWER: $ (复杂度优化) 题目大意:统计可重序列中最长上升子序列的方案数. 题目很直接的说明了所求为 $ L ...
-
kuangbin带你飞dp专题-基础dp
dp HDU - 1257 最少拦截系统 最长递增子序列 #include<iostream> using namespace std; const int maxn=1e7; int a ...
-
[Java]刷题中的Java基础
数组 取数组长度是属性length ArrayList ArrayList<Integer> maxRootHeap = new ArrayList<Integer>(); m ...
-
再也不用c刷题了!!——c++刷题必备
致读者: 博主是一名数据科学与大数据专业大二的学生,真正的一个互联网萌新,写博客一方面是为了记录自己的学习历程,一方面是希望能够帮助到很多和自己一样处于困惑的读者.由于水平有限,博客中难免会有一些错误 ...
-
DP刷题记录(持续更新)
DP刷题记录 (本文例题目前大多数都选自算法竞赛进阶指南) TYVJ1071 求两个序列的最长公共上升子序列 设\(f_{i,j}\)表示a中的\(1-i\)与b中色\(1-j\)匹配时所能构成的以\ ...
-
DP刷题记录
目录 dp刷题记录 codeforces 706C codeforces 940E BZOJ3997 POJ2279 GYM102082B GYM102082D codeforces132C L3-0 ...
-
【刷题笔记】DP优化-状压
因为篇幅太长翻着麻烦,计划把DP拆成几个小专题,这里原文只留下状压,其他请至后续博文. 状态压缩优化 所谓状态压缩,就是将原本需要很多很多维来描述,甚至暴力根本描述不清的状态压缩成一维来描述. 时间复 ...
-
刷题总结——bzoj1725(状压dp)
题目: 题目描述 Farmer John 新买了一块长方形的牧场,这块牧场被划分成 N 行 M 列(1<=M<=12; 1<=N<=12),每一格都是一块正方形的土地. FJ ...
-
刷题总结——选课(ssoj树形dp+记忆化搜索+多叉树转二叉树)
题目: 题目描述 学校实行学分制.每门的必修课都有固定的学分,同时还必须获得相应的选修课程学分.学校开设了 N(N<300)门的选修课程,每个学生可选课程的数量 M 是给定的.学生选修了这M门课 ...
随机推荐
-
在Dynamics CRM 2015中通过3CX插件(以及3CX windows phone)拨出电话
背景 在On-premises部署的Dynamics CRM中实现通过网页拨通客户电话的功能 要点 3CX 提供了开箱即用的Dynamics CRM Solution,只需要在Microsoft Dy ...
-
NOTES : A Model of Gas Exchange for Hyperpolarized Xe(129) Magnetic Resonance of the Lung
NOTES : A Model of Gas Exchange for Hyperpolarized Xe(129) Magnetic Resonance of the Lung 背景知识: Ga ...
-
Android编程之SparseArray<;E>;详解
最近编程时,发现一个针对HashMap<Integer, E>的一个提示: 翻译过来就是:用SparseArray<E>来代替会有更好性能.那我们就来看看源码中SparseAr ...
-
(转)Permission denied: win7下面eclipse上传本地文件到DFS &;&; 运行M/R程序时出现的同样的错误解决方法
原文地址: http://mntms.iteye.com/blog/2095651 hadoopeclipse远程控制权限 情景一: 当在win7下面的eclipse装好插件,首次运行M/R程序的时 ...
-
nginx+python+windows 开始
参考文章:http://www.testwo.com/article/311 参考如上文章基本能够完成hello world示例,我来记录下自己操作步骤及不同点,用以备忘,如果能帮助到其他人更好. 以 ...
-
Java面试题以及答案精选(架构师面试题)-基础题1
基础题 一.String,StringBuffer, StringBuilder 的区别是什么?String为什么是不可变的?1. String是字符串常量,StringBuffer和StringBu ...
-
VsCode下代码导航
Visual Studio Code具有高效的代码编辑器,当与编程语言服务结合使用时,可以为您提供IDE的强大功能和文本编辑器的速度.在本主题中,我们将首先描述VS Code的语言智能功能(建议,参数 ...
-
JAVAWEB 一一SpringMVC(XML配置)
web.xml <?xml version="1.0" encoding="UTF-8"?> <web-app version="2 ...
-
GDI基础(1):绘制线条和图形
1. 绘制一个像素点:SetPixel(). 绘制直线:MoveTo(),LineTo(). 绘制多个首尾相连的线:Polyline(). 绘制矩形:FrameRect(),Rectangle(),F ...
-
C# CSGL
转.修改自ShareIdeas文章C# 基于CSGL opengl OpenGL是一个功能强大的开放图形库(Open Graphics Library).其前身是SGI公司为其图形工作站开发的IRIS ...