20180418模拟赛T1——Seq
Seq
(seq.cpp/c/pas)
题目描述 Description
木吉要去征讨VAN様,所以他现在需要从他身边的人中选出若干位陪同。现在有\(n\)个人站成一行,木吉要从其中选出\(2\)批在这一行中连续的人(不能不选),且一个人不能两次都被选。每位人有一个战斗力\(A_i\),\(A_i\)可正可负。木吉团队的战斗力即为选择的人的\(A_i\)之和。
现在木吉想要知道最大的战斗力是多少。
输入描述 Input Description (seq.in)
第一行为人数\(n\),第二行为\(n\)个整数依次为\(A_1,A_2,\cdots,A_n\)
输出描述 Output Description (seq.out)
一个整数,即为最大的战斗力之和
样例输入 Sample Input
6
10 -5 6 0 0 1
样例输出 Sample Output
17
样例解释 Sample Interpretation
第一批只选第一个人,第二批选第三、四、五、六个人
数据范围 Data Size
对于\(30\%\)的数据,\(n\le 50\),\(A_i\)的绝对值不超过\(1000\)
对于\(60\%\)的数据,\(n\le 5000\),\(A_i\)的绝对值不超过\(100000\)
对于\(100\%\)的数据,\(n\le 100000\),\(A_i\)的绝对值不超过\(1000000000\)
题解
这张试卷中的人物名有点毒瘤
一眼看是一道dp,于是开始大力转移。
由于是分两批,于是想到需要分段处理。
第\(i\)号位置为最右端点的方案中最大战斗力为\(ll[i]\),同理定义\(rr[i]\)。
那么显然有:\(ll[i]=x[i]+max(ll[i-1],0),rr[i]=x[i]+max(rr[i+1],0)\)(贪心一下即可:如果前一位的最大值大于0,那么就加上前一位;否则就不加)。
设\(lll[i]\)为前\(i\)位的最优方案,同理定义\(rrr[i]\)(好吧我承认我的变量名有毒)。
于是我们就可以很容易地推出:\(lll[i]=max(lll[i-1],ll[i]),rrr[i]=max(rrr[i+1],rr[i])\)(选与不选第\(i\)位)。
最终,我们枚举断点(分成两段处理,取最大值):\(ans=max(ans,lll[i]+rrr[i+1])\)。
代码如下
#include <cstdio>
#include <cctype>
#include <iostream>
using namespace std;
typedef long long LL;
#define dd c=getchar()
inline void read(LL& x)
{
x=0;int dd;bool f=false;
for(;!isdigit(c);dd)if(c=='-')f=true;
for(;isdigit(c);dd) x=(x<<1)+(x<<3)+(c^48);
if(f)x=-x;return;
}
#undef dd
const LL INF=0x3f3f3f3f3f3f3f3f;
const LL maxn=100005;
LL ll[maxn],rr[maxn];
LL lll[maxn],rrr[maxn];
LL x[maxn];
int main()
{
freopen("seq.in","r",stdin);
freopen("seq.out","w",stdout);
LL n;read(n);
lll[0]=rrr[n+1]=-INF;
for(LL i=1;i<=n;++i)
{
read(x[i]);
ll[i]=x[i]+max(ll[i-1],0LL);
}
for(LL i=n;i;--i)
rr[i]=x[i]+max(rr[i+1],0LL);
LL ans=-INF;
for(LL i=1;i<=n;++i)
lll[i]=max(lll[i-1],ll[i]);
for(LL i=n;i;--i)
rrr[i]=max(rrr[i+1],rr[i]);
for(int i=1;i<n;++i)
ans=max(ans,lll[i]+rrr[i+1]);
printf("%lld",ans);
fclose(stdin);
fclose(stdout);
return 0;
}
最新文章
- MySQLdb的一些经验
- Java泛型详解 转载
- 2014 Super Training #6 H Edward&#39;s Cola Plan --排序+二分
- JVM垃圾收集策略解析
- 8个必备的PHP功能开发 (转)
- Docker Machine
- Math对象
- VS C++工程类成员初始化检测脚本
- 【我的书】Unity Shader的书 — 文件夹(2015.12.21更新)
- java 类与类之间的关系 及uml图
- Day-10: 错误、调试和测试
- WebUploader上传文件(一)
- s遇到错误不要慌,教你方法走四方
- 树莓派初体验,安装Ubuntu 14.04 LTS
- 某公司基于FineBI数据决策平台的试运行分析报告
- 2017-10-22&mdash;LD激光二极管原理
- Spark 灰度发布在十万级节点上的成功实践 CI CD
- C++ Template 编程,泛型编程练习
- number (2)编译错 (类的大小写错误) Filewriter cannot be resolved to a type
- DesignMode的重载 C#
热门文章
- vux scroller在iOS13上,一停止滑动就跳到顶部
- 从零开始学C语言
- U9数据权限分配枚举值方法
- CSP2019-S宝典
- 动态代理(一)——JDK中的动态代理
- subjective--主观
- 【mysql】mysql5.7支持的json字段查询【mybatis】
- 使用el-dialog时,报错“Unknown custom element:<;el-dialog>; did you register the component correctly?...make sure to provide the &#39;name&#39; option”
- chrome安装插件
- 使用JavaConfig配置SpringMVC