Loj 507 接竹竿 题解

Loj链接:接竹竿


$ {\scr \color {SkyBlue}{\text{Solution}}} $

题目大意:

给定一个数组,每次加入一种颜色的数,可以取走与它颜色相同的两个数之间的所有数,问最后取走的所有数中最大和是多少

分析:

第一眼看到的是二分答案,但不知道二分的check()函数怎么写。

没办法,考虑DP(其实是因为我贪心写挂了)

DP如果可以,那么要至少要满足一下几个条件:

  1. DP前面的选择情况不影响后面的选择情况(前不影响后)
  2. DP可以转移

时间、空间复杂度等可以以后慢慢优化啦!

 尝试一下?

尝试列出转移方程:

$$dp[i]=max \begin{cases} dp[i-1]& \text{$c_i$}!={c_j}\\ dp[j-1] +   \sum_{k=1}^{i} v_k -    \sum_{k=1}^{j-1} v_k  & \text{$c_i==c_j$} \end{cases}$$ 

这样我们就列出了一个$O(n^3)$的DP转移方程。

接下来就考虑优化呗!

优化

  1. 前缀和优化

易发现,DP方程里有很多类似求$\sum_{i}^{j} v_k$的,并且每次DP推方程时都要重新计算一遍

其实,求连续一段值的和,我们可以用前缀和优化啊!

现在方程就是$O(n^2)$的了。

示例代码(会TLE!):

for(int i=1;i<=n;i++) scanf("%lld",&a[i].y),a[i].y+=a[i-1].y;
for(int i=1;i<=n;i++)
{
    dp[i]=dp[i-1];
    for(int j=1;j<i;j++)
    if(a[i].x==a[j].x) dp[i]=max(dp[i],dp[j-1]+a[i].y-a[j-1].y);
}

考虑进一步优化

发现转移时,只能找与自己颜色相同的进行转移,所以可以把每一个颜色记录下来,省下循环过程。

这可以用链表或者$ \cal{vector}$ 实现

注意:时间复杂度此时是可以被卡到$O(n^2)$的!因为并没有剩下转移过程,只是省去了枚举无法转移情况的时间。

代码就不放辣QwQ!

再来看看这个转移方程:

$$dp[i]=max \begin{cases} dp[i-1]& \text{$c_i$}!={c_j}\\ dp[j-1] +   \sum_{k=1}^{i} v_k -    \sum_{k=1}^{j-1} v_k  & \text{$c_i==c_j$} \end{cases}$$ 

我们可以把$\cal{dp[i]}$的初值赋为$\cal{dp[i-1]}$

那就只要考虑这个:

$$dp[i]=max \begin{cases}  dp[j-1] +   \sum_{k=1}^{i} v_k -    \sum_{k=1}^{j-1} v_k  & \text{$c_i==c_j$} \end{cases}$$ 

用前缀和优化后:

$$dp[i]=max \begin{cases}  dp[j-1] +   summ[i]-    summ[j-1]  & \text{$c_i==c_j$} \end{cases}$$ 

我们稍稍改变一下转移方程顺序:

$$dp[i]=max \begin{cases}   summ[i]+(dp[j-1]  -   summ[j-1])  & \text{$c_i==c_j$} \end{cases}$$ 

换句话说,我们只要求出与$c_i$相等颜色里,$dp[j-1]  -  summ[j-1] $ 最大值

这个可以用一个数组记下来啊!

那么只要$\cal{O(1)}$,就能完成转移

时间复杂度:$ \cal{O(n)}$

Code:

#include<bits/stdc++.h>
#define L long long
using namespace std;
struct P{
    int x;
    L y;
}a[1000005];
L dp[1000005],maxx[1000005];
signed main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++) scanf("%d",&a[i].x);
    for(int i=1;i<=k;i++) maxx[i]=-1e18;
    for(int i=1;i<=n;i++) scanf("%lld",&a[i].y),a[i].y+=a[i-1].y;
    for(int i=1;i<=n;i++)
    {
        dp[i]=max(dp[i-1],maxx[a[i].x]+a[i].y);
        maxx[a[i].x]=max(maxx[a[i].x],dp[i-1]-a[i-1].y);
    }
    printf("%lld",dp[n]);
    return 0;
}
本文转载于网络 如有侵权请联系删除

相关文章

  • 哈佛专家披露:马斯克侵入式脑机接口技术的三个进展与三大局限

    【新智元导读】8月底,马斯克和三只小猪的发布会震惊了脑科学界。而对于马斯克发布的侵入式脑机接口技术的进展和局限,哈佛大学脑科学博士、BrainCo创始人韩璧丞,哈佛大学医学院科学家、康谱睿启脑科学负责人杨锦陈进行了独家解读。美国时间8月28日下午,侵入式脑机接口技术公司Neuralink的创始人、科技英雄「硅谷钢铁侠」埃隆-马斯克举行了他戏称为「三只小猪」的发布会。通过「遛猪」的方式,向世界宣布和展示了Neuralink团队在过去一年里取得的研发成果,再次将「脑机接口」概念推到了全球关注的焦点。很多人首先惊讶于猪的登场,也为在发布会上听见了猪大脑细胞放电的「声音」而兴奋不已。事实上,这在神经科学领域均属于常规操作。将记录到的神经细胞放电转化成为声波播放出来,电生理学研究者们已经在实验室里听了几十年。而猪的头很大,是做神经植入术的理想实验品。比如,2015年麻省理工学院的一篇博士论文研究就在猪头上试验植入了可以长期记录和诊断癫痫脑电波的装置(见下图,来源https://dspace.mit.edu/,作者BrunoG.DoValle)。与ElonMusk的发布异曲同工,包括其中溜猪环节。

  • PHP反序列化字符串逃逸

    文章源自【字节脉搏社区】-字节脉搏实验室作者-purple0x00前提掌握PHP反序列化的原理,序列化的对应内容及POP链构造。可参看:https://xz.aliyun.com/t/3674,https://xz.aliyun.com/t/6454PHP的反序列化特点:01.PHP在反序列化时,底层代码是以;作为字段的分隔,以}作为结尾(字符串除外),并且是根据长度判断内容的,同时反序列化的过程中必须严格按照序列化规则才能成功实现反序列化。例如下图超出的abcd部分并不会被反序列化成功。02.当长度不对应的时候会出现报错03可以反序列化类中不存在的元素输出:0x01字符串逃逸此类问题分为两种:1-过滤后字符变多,2-过滤后字符变少。1-过滤后字符变多的原理就是引用的闭合思想。案列Demo:该Demo的输出结果就可以看到p被换成了两个W,而前面对应的数值仍然是没过率之前的7。而后面的报错注意,也就是上面所说的特点2的性质。而也是因为有这个过滤的存在,所以存在了注入的漏洞,我们可以构造序列化字符修改age的值,构造修改age的值的代码:";i:1;s:2:"20&qu

  • 基于Mixin Network的PHP比特币开发教程: 创建比特币钱包

    我们已经创建过一个回复消息的机器人和一个能自动支付比特币的机器人.通过本教程的学习,你可以学到如下内容如何创建一个比特币钱包.如何读取比特币钱包的余额.如何支付比特币并即时确认.如何将MixinNetwork的比特币提现到你的冷钱包或第三方交易所.前期准备:你要有一个MixinNetwork账户。如果没有账户,一行代码就能创建一个$user_info=$mixinSdk->Network()->createUser("Tomcat");复制上面的语句会在本地创建一个RSA密钥对,然后调用MixinNetwork来创建帐号,最后输出帐号信息.//CreateUserapiincludeallaccountinformation print_r($user_info); print($user_info["pubKey"]); $newConfig=array(); $newConfig["private_key"]=$user_info["priKey"]; $newConfig["pi

  • 严格别名规则“-fstrict-aliasing”和“-fno-strict-aliasing”及类型双关

    “-fstrict-aliasing”表示启用严格别名规则,“-fno-strict-aliasing”表示禁用严格别名规则,当gcc的编译优化参数为“-O2”、“-O3”和“-Os”时,默认会打开“-fstrict-aliasing”。 什么是严格别名规则?gcc对严格别名的定义:In particular, an object of one type is assumed never to reside at the same address as an object of a different type, unless the types are almost the same. 即,编译器假定相同的内存地址绝不会存放不同类型的数据,否则即破坏了严格别名规则。复制 别名的定义可理解为:同一内存地址有不同的名称,比如:int m = 0x20190101; int* p1 = &m; int *p2 = &m; int *p3 = p2; int n = m;复制 这里“&m”、“p1”、“p2”和“p3”均是同一内存地址的别名,但n不是,因此涉及严格别

  • TensorFlow实战——RNN(LSTM)——预测sin函数

    http://blog.csdn.net/u011239443/article/details/73650806关于LSTM可以参阅:http://blog.csdn.net/u011239443/article/details/73196473 完整代码:https://github.com/xiaoyesoso/TensorFlowinAction/blob/master/InActionB1/chapter8/sinModel.py数据我们先来看下需要产生的数据,我们每隔SAMPLE_GAP采样一个点:test_start=TRAINING_EXAMPLES*SAMPLE_GAP test_end=(TRAINING_EXAMPLES+TESTING_EXAMPLES)*SAMPLE_GAP复制TRAINING_EXAMPLES为训练样本的个数,TESTING_EXAMPLES为测试样本的个数。那么可知训练集的样本点落在[0,test_start)[0,test\_start)上,而测试集的样本落在[test_start,test_end)[test\_start,test\_e

  • 创意网页排版设计和教程分享,打造 “视”不可挡的网页设计

    网页中超过95%以上的信息都是通过文字的形式呈现。然而,页面文字并非毫无章法的随意呈现。事实上,更具可读性、视觉效果以及独特排版和布局的网页文本设计,更能吸引用户,提升用户愉悦度。这也是为什么越来越多的设计师日益重视网页排版设计的重要原因。因此,在相继分析网页情感化设计,网页UI文案设计以及网页视觉层级设计之后,Mockplus为大家整理了17款最新创意网页排版设计和相关教程。和大家一起探讨,作为设计师,应该如何进行网页排版设计,增强页面视觉魅力的同时,快速引导用户,提升用户体验。1.PittoriDiCinema设计师: Bunker网页类型:艺术类网站亮点:简约大胆的首屏排版设计简约的背景,配合大胆直观的粗体文本设计,是最近几年日益流行起来的网站排版方式。而本款单页艺术类网站就采用这一设计理念,利用超大粗体设计突出页面内容,直观时尚。其独特的文本字体,也极具吸引力。恰到好处的网页配色,也使页面更加美观吸睛。学习点:利用简约直观的粗体文本设计,突出页面主题内容文字越大,越突出,就越能引起用户的注意。简约大胆的粗体文本设计,结合图标,色彩以及动效的变化,突出文本内容的同时,能够有效地赋

  • 深度森林deep-forest | ImportError: cannot import name ‘_joblib_parallel_args‘ from ‘sklearn.utils.fixes‘

    实践深度森林算法(deep-forest),安装了相应的模块,但是在调用的时候,scikit-learn中的函数一直报错,遇到报错如下:pipinstalldeep-forest fromdeepforestimportCascadeForestClassifier复制明显是sklearn版本问题导致的,调用api的方法不对应了。解决方法:降低scikit-learn的版本,pipinstalldeep-forest默认安装的版本:scikit-learn1.1.2,使用命令卸载高版本scikit-learn,然后安装scikit-learn1.0.2。pipuninstallscikit-learn pipinstallscikit-learn==1.0.2复制然后可以成功运行代码了~~GithubIssue|Unabletoimportjoblibafterupdateto1.1.0#23383GithubIssue|[BUG]_joblib_parallel_argsremovedinlatestscikit-learndevbuild#894

  • 车牌检测STN:Spatial Transformer Networks

    参考文献:MaxJaderberg,KarenSimonyan,AndrewZisserman,KorayKavukcuoglu.SpatialTransformerNetworks,2016.linkSpatialTransformerNetworks空间变换网络MaxJaderberg,KarenSimonyan,AndrewZisserman,KorayKavukcuoglu摘要卷积神经网络定义了一类异常强大的模型,但仍然受到缺乏在计算和参数效率方面对输入数据具有空间不变性的能力的限制。在这项工作中,我们引入了一个新的可学习模块,即空间转换器,它明确地允许在网络中对数据进行空间操作。该可微模块可以插入到现有的卷积结构中,使神经网络能够主动地在特征映射本身上有条件地变换特征映射,而无需任何额外的训练监督或修改优化过程。我们表明,使用空间变换器会导致模型学习到对平移、缩放、旋转和更一般的扭曲不变性,从而在多个基准和多个变换类上获得最先进的性能。1引言近年来,通过采用一种快速、可扩展、端到端的学习框架,即卷积神经网络(CNN)[21],计算机视觉的前景发生了巨大的变化并得到了推进。虽然

  • 手把手教你掌握——性能工具Jmeter之参数化(含安装教程 )

    本节大纲 Jmeter发送get/post请求 Jmeter之文件参数化-TXT/Csv Jmeter之文件参数化-断言 JMeter简介 ApacheJMeter是一款基于JAVA的压力测试T具编写负载功能测试和性能测试开源工具软件。 Apachejmeter可以用于对静态的和动态的资源(文件,Servlet,Perl脚本,java对象,数据库和查询,FTP服务器等等)的性能进行测试。它可以用于对服务器、网络或对象模拟繁重的负载来测试它们的强度或分析不同压力类型下的整体性能。你可以使用它做性能的图形分析或在大并发负载测试你的服务器/脚本/对象 性能工具 相比Loadrunner而言,JMeter小巧轻便且免费,逐渐成为了主流的性能测试工具,是每个测试人员都必须要掌握的工具之一。 发送请求实例-GET请求 新闻列表查询 接口地址:http://v.juhe.cn/toutiao/index返回格式:json请求方式:get请求示例:http://vjuhe.cn/toutiao/index?type=top&key=Of7190a8

  • 353 stars Java项目!Java小白必看!austin介绍 【第一话】

    有好几个群友问我为什么最近更新变慢了。工作忙是一方面,另一方面是我更新文章的动力确实下降了。近大半年一直在更新的《对线面试官》系列,到现在已经40篇了。 说实话,当时我更新该系列有很大一部分是为了自己的面试。而现在入职了以后,短时间内也不会跳槽了,所以更新该系列的动力就自然下降了。 话说回来,我前段时间在面试的时候,照着《对线面试官》系列所准备的知识,基本都没太大的问题。 最近我在工作做的事情还需要不少的时间沉淀,短时间内又写不出比较好的文章跟大家一起分享。 基于以上的问题,这段时间就好像进入了死循环,出不来了。 01、想法 有很长的一段时间,我都在想要不要写个「小项目」持续迭代。 这样一来,我在空闲的时间就可以继续写代码了,并且在写项目的过程中又会潜意识督促自己不断地学习。 之前空闲的时间都在码文章和学习,基本没怎么写代码的(: 在工作倒是一直写代码,只不过写的代码都不是我喜欢的。 虽然自己的代码写得很烂,但自己并不觉得自己的代码很烂。很多时候感觉自己的代码写得挺好的,而同事进来做了一把需求,感觉代码又变烂了。有没有人跟我有相同的想法? 自从毕业工作了以后,就越来越发现自己所

  • 春招面经——网易互娱服务端开发一面

    一、前言   刚刚面完网易互娱服务端开发(实习)一面,面完就想抽自己,怎么能这么菜。唉,先不多说,直接进入正题。 二、正文 1、面试官提问 1、自我介绍 答:唉,太菜了,没什么额外介绍的,直接背简历了(;´༎ຶД༎ຶ`)。 2、介绍一下Java中的引用类型? 答:强引用,软引用,弱引用,虚引用。然后简单介绍了一下他们的作用以及JDK提供什么类使用这些引用(虚引用的类名记不清了,直接说了P打头的一个类......)。 3、为什么需要这些引用? 答:我直接拿ThreadLocal中的ThreadLocalMap,它的key是弱引用举例,讲了一下为什么需要这些特殊的引用。总结下来就是防止已经不需要的引用影响垃圾回收。 4、介绍一下垃圾回收算法? 答:引用计数、可达性分析、标记-清除、复制算法、标记整理。 5、如何判断链表有环? 答:快慢指针。 6、还是上面这题,有没有可能出现快指针跳过慢指针,导致判断错误? 唉,这里后面想想真是想抽自己。这个问题之前考虑过,这里一下没反应过来,就说这个我之前想过,我思考一下(我居然傻了吧唧地说之前想过,这不就让面试官觉得我在背答案吗(

  • psi计算

    基础概念:https://zhuanlan.zhihu.com/p/344754828 importsys importpandasaspd importnumpyasnp importmath #all_list=[] #df=pd.DataFrame(columns=['date','data']) #counter=0 #forlineinsys.stdin: #line=line.strip('\r\n') #df.loc[counter]=line.split(',') #counter+=1 #df.to_excel('./output2.xlsx',sheet_name='Sheet1') defcalc_psi(dataframe): date_col=dataframe['date'] data_col=dataframe['data'] #print(dataframe['data'].max(),dataframe['data'].min()) #分组 result=pd.qcut(dataframe['data'],10) #print(result)

  • C#基础笔记——协变(Covariance)和逆变(Contravariance)

    一、概述 协变是指返回类型返回比声明的类型派生程度更大的类型,关键字:out。 逆变是指方法的参数可以是委托或者泛型接口的参数类型的基类,关键字:in。FCL4.0中支持逆变的常用委托有:Func<inT,outTResult>,Predicate<inT>。 二、泛型中协变事例   classProgram { staticvoidMain(string[]args) { ISalary<Programer>s=newBaseSalaryCounter<Programer>(); printSalary(s); Console.ReadKey(); } privatestaticvoidprintSalary(ISalary<Employee>s) { s.Pay(); } } //interfaceISalary<T>//这样写会导致编译报错 interfaceISalary<outT> { voidPay(); } classBaseSalaryCounter<T>:IS

  • Springboot集成Redis举例

    依赖包 <dependency> <groupId>org.springframework.boot</groupId> <artifactId>spring-boot-starter-data-redis</artifactId> </dependency>复制   配置文件(application.properties) #Redis数据库索引(默认为0) spring.redis.database=0 #Redis服务器地址 spring.redis.host=x.x.x.x #Redis服务器连接端口 spring.redis.port=6738 #Redis服务器连接密码(默认为空) spring.redis.password= #连接超时时间(毫秒) spring.redis.timeout=10000 #连接池最大连接数(使用负值表示没有限制) spring.redis.jedis.pool.max-active=8 #连接池最大阻塞等待时间(使用负值表示没有限制) spring.re

  • 3.ftplinux系统用户登录实验

    把所有的linux系统用户映射成来宾用户,来宾用户是ftp用户,也就是匿名用户,这些用户访问的目录默认都是/var/ftp/pub #防止用户切换到/目录,所有用户映射成一个普通用户 guest_enable=YES#开启账号映射 guest_username=ftp#映射为ftp,配合`guest_enable=YES`使用 local_root=/data/ftpshare 复制 基于上面文件的实验,实现系统用户登录.可以上传文件 mkdir/data/ftpshare/upload/ chmod777/data/ftpshare/upload/ 注意:给目录授权要给/data/ftpshare根目录授权否则不能登录.要给根目录下的upload子目录授权 复制 3.以下文件实现,系统用户映射为guess用,上传下载文件 点击查看代码 mkdir/data/ftpshare/upload/ chmod777/data/ftpshare/upload/ #Exampleconfigfile/etc/vsftpd/vsftpd.conf # #Thedefaultcompi

  • bzoj 1070 费用流

    //可以网络流,但是要怎么分配每辆车让谁维修以及维修顺序呢。可以考虑每辆车维修时间对总结果的贡献,把每个修车人拆成n个点共n*m个点, //n辆车连向这n*m个点,流量1,费用k*修车时间,其中k(1=<k<=n)表示这辆车是这个技术人员修的倒数第k俩车,他后面k-1辆被同一个人维修的车 //都要等待他修好,因此他的贡献值就是k*维修时间。然后源点连向n辆车,n*m个点连向汇点。 #include<iostream> #include<cstdio> #include<cstring> #include<queue> usingnamespacestd; constintINF=0x7fffffff; constintMAXN=1000; constintMAXM=1000000; intN,a[70][12],tot,head[MAXN+10],pre[MAXN],dis[MAXN]; boolvis[MAXN+10]; structEdge { intto,next,cap,flow,cost; }edge[MAXM+

  • 为phpStorm 配置PHP_CodeSniffer自动检查代码

    通过composer安装PHP_CodeSniffer: squizlabs/PHP_CodeSniffergihub地址   composerglobalrequire"squizlabs/php_codesniffer=*" 配置phpStorm找到phpcs.bat的路径之后valiedate验证一下   用上一个路径可以,下面一个会报错: inspections(检查)   效果如下:  

  • GIT应用

    1.Git概念 1.1.Git库中由三部分组成       Git仓库就是那个.git目录,其中存放的是我们所提交的文档索引内容,Git可基于文档索引内容对其所管理的文档进行内容追踪,从而实现文档的版本控制。.git目录位于工作目录内。 1)工作目录:用户本地的目录; 2)Index(索引):将工作目录下所有文件(包含子目录)生成快照,存放到一个临时的存储区域,Git称该区域为索引。 3)仓库:将索引通过commit命令提交至仓库中,每一次提交都意味着版本在进行一次更新。 1.2.使用Git时的初始化事项 1.2.1.Git初始化配置 1)配置使用git仓库的人员姓名       gitconfig--globaluser.name"YourNameComesHere" 2)配置使用git仓库的人员email      

  • 上传XML文件字符编码问题

    1、上传的XML文件的空格的字符编码和倒入到数据库的空格的字符编码不是一种编码格式,导致导入到数据库的数据和XML文件的数据不一致的情况,进而使展示到界面上的数据在进行搜索时不能搜索出来。解决办法: stringasciiSpace=char.ConvertFromUtf32(32); stringChineseSpace=char.ConvertFromUtf32(160);复制 labor.Description=description.Replace(ChineseSpace,asciiSpace); 强制将导入的数据的字符编码替换掉。

  • services 系统服务的启动、停止、卸载

    MySQL服务的启动、停止与卸载 在Windows命令提示符下运行: 启动: netstartMySQL 停止: netstopMySQL 卸载: scdeleteMySQL   Scdelete说明 Scdelete是WindowsDOS命令,用于删除Windows服务,从注册表中删除服务子项。如果服务正在运行或者另一个进程有一个该服务的打开句柄,那么为了删除而标记该服务。此命令适用于:Windows7,WindowsServer2003,WindowsServer2003R2,WindowsServer2003withSP1,WindowsServer2003withSP2,WindowsServer2008,WindowsServer2008R2,WindowsVista。 语法 sc[ServerName]delete[ServiceName] 参数 [ServerName] 指定服务所在的远程服务器名称。该名称必须使用UNC格式("\\myserver")。若要在本机上运行SC.exe,请忽略此参数。 [ServiceName]  

  • android 保存图片,及将图片更新到图库

     **保存图片 publicstaticFilesaveImage(Bitmapbmp){ FileappDir=newFile(Environment.getExternalStorageDirectory(),"文件夹名字"); if(!appDir.exists()){ appDir.mkdir(); } StringfileName=System.currentTimeMillis()+".jpg"; Filefile=newFile(appDir,fileName); try{ FileOutputStreamfos=newFileOutputStream(file); bmp.compress(CompressFormat.JPEG,100,fos); fos.flush(); fos.close(); }catch(FileNotFoundExceptione){ e.printStackTrace(); }catch(IOExceptione){ e.printStackTrace(); } }复制 **把文件插入图库 try{ MediaStore.I

相关推荐

推荐阅读