刷题向》DP》关于基础DP(easy)

时间:2022-09-08 07:47:02

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)的更多相关文章

  1. &dollar;2019&dollar; 暑期刷题记录1&colon;&lpar;算法竞赛DP练习&rpar;

    $ 2019 $ 暑期刷题记录: $ POJ~1952~~BUY~LOW, BUY~LOWER: $ (复杂度优化) 题目大意:统计可重序列中最长上升子序列的方案数. 题目很直接的说明了所求为 $ L ...

  2. kuangbin带你飞dp专题-基础dp

    dp HDU - 1257 最少拦截系统 最长递增子序列 #include<iostream> using namespace std; const int maxn=1e7; int a ...

  3. &lbrack;Java&rsqb;刷题中的Java基础

    数组 取数组长度是属性length ArrayList ArrayList<Integer> maxRootHeap = new ArrayList<Integer>(); m ...

  4. 再也不用c刷题了&excl;&excl;——c&plus;&plus;刷题必备

    致读者: 博主是一名数据科学与大数据专业大二的学生,真正的一个互联网萌新,写博客一方面是为了记录自己的学习历程,一方面是希望能够帮助到很多和自己一样处于困惑的读者.由于水平有限,博客中难免会有一些错误 ...

  5. DP刷题记录&lpar;持续更新&rpar;

    DP刷题记录 (本文例题目前大多数都选自算法竞赛进阶指南) TYVJ1071 求两个序列的最长公共上升子序列 设\(f_{i,j}\)表示a中的\(1-i\)与b中色\(1-j\)匹配时所能构成的以\ ...

  6. DP刷题记录

    目录 dp刷题记录 codeforces 706C codeforces 940E BZOJ3997 POJ2279 GYM102082B GYM102082D codeforces132C L3-0 ...

  7. 【刷题笔记】DP优化-状压

    因为篇幅太长翻着麻烦,计划把DP拆成几个小专题,这里原文只留下状压,其他请至后续博文. 状态压缩优化 所谓状态压缩,就是将原本需要很多很多维来描述,甚至暴力根本描述不清的状态压缩成一维来描述. 时间复 ...

  8. 刷题总结——bzoj1725(状压dp)

    题目: 题目描述 Farmer John 新买了一块长方形的牧场,这块牧场被划分成 N 行 M 列(1<=M<=12; 1<=N<=12),每一格都是一块正方形的土地. FJ  ...

  9. 刷题总结——选课(ssoj树形dp&plus;记忆化搜索&plus;多叉树转二叉树)

    题目: 题目描述 学校实行学分制.每门的必修课都有固定的学分,同时还必须获得相应的选修课程学分.学校开设了 N(N<300)门的选修课程,每个学生可选课程的数量 M 是给定的.学生选修了这M门课 ...

随机推荐

  1. 在Dynamics CRM 2015中通过3CX插件&lpar;以及3CX windows phone&rpar;拨出电话

    背景 在On-premises部署的Dynamics CRM中实现通过网页拨通客户电话的功能 要点 3CX 提供了开箱即用的Dynamics CRM Solution,只需要在Microsoft Dy ...

  2. NOTES &colon; A Model of Gas Exchange for Hyperpolarized Xe&lpar;129&rpar; Magnetic Resonance of the Lung

    NOTES :  A Model of Gas Exchange for Hyperpolarized Xe(129) Magnetic Resonance of the Lung  背景知识: Ga ...

  3. Android编程之SparseArray&lt&semi;E&gt&semi;详解

    最近编程时,发现一个针对HashMap<Integer, E>的一个提示: 翻译过来就是:用SparseArray<E>来代替会有更好性能.那我们就来看看源码中SparseAr ...

  4. (转)Permission denied&colon; win7下面eclipse上传本地文件到DFS &amp&semi;&amp&semi; 运行M&sol;R程序时出现的同样的错误解决方法

    原文地址: http://mntms.iteye.com/blog/2095651 hadoopeclipse远程控制权限  情景一: 当在win7下面的eclipse装好插件,首次运行M/R程序的时 ...

  5. nginx&plus;python&plus;windows 开始

    参考文章:http://www.testwo.com/article/311 参考如上文章基本能够完成hello world示例,我来记录下自己操作步骤及不同点,用以备忘,如果能帮助到其他人更好. 以 ...

  6. Java面试题以及答案精选(架构师面试题)-基础题1

    基础题 一.String,StringBuffer, StringBuilder 的区别是什么?String为什么是不可变的?1. String是字符串常量,StringBuffer和StringBu ...

  7. VsCode下代码导航

    Visual Studio Code具有高效的代码编辑器,当与编程语言服务结合使用时,可以为您提供IDE的强大功能和文本编辑器的速度.在本主题中,我们将首先描述VS Code的语言智能功能(建议,参数 ...

  8. JAVAWEB 一一SpringMVC&lpar;XML配置&rpar;

    web.xml <?xml version="1.0" encoding="UTF-8"?> <web-app version="2 ...

  9. GDI基础(1):绘制线条和图形

    1. 绘制一个像素点:SetPixel(). 绘制直线:MoveTo(),LineTo(). 绘制多个首尾相连的线:Polyline(). 绘制矩形:FrameRect(),Rectangle(),F ...

  10. C&num; CSGL

    转.修改自ShareIdeas文章C# 基于CSGL opengl OpenGL是一个功能强大的开放图形库(Open Graphics Library).其前身是SGI公司为其图形工作站开发的IRIS ...