| 题目名称 | 2062. [ZLXOI 2015][异次元圣战II]燃灵之链 |
|---|---|
| 输入输出 | KPengshuangcang.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 Satoshi
于2015-10-18加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：21， 提交：48， 通过率：43.75% | ||||
 _Itachi |
100 | 0.025 s | 0.13 MiB | C++ |
 Go灬Fire |
100 | 0.032 s | 0.24 MiB | C++ |
 devil |
100 | 0.047 s | 0.32 MiB | C++ |
|
Go灬Fire |
100 | 0.059 s | 0.30 MiB | C++ |
 KZNS |
100 | 0.090 s | 76.78 MiB | C++ |
|
KZNS |
100 | 0.097 s | 76.78 MiB | C++ |
|
Go灬Fire |
100 | 0.099 s | 0.21 MiB | C++ |
|
KZNS |
100 | 0.107 s | 0.33 MiB | C++ |
|
梦那边的美好ET |
100 | 0.117 s | 3.26 MiB | C++ |
 mikumikumi |
100 | 0.150 s | 0.34 MiB | C++ |
| 本题关联比赛 | |||
| ZLXOI2015Day1 | |||
| 关于 燃灵之链 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
回复 @叶子の宿敌 :
现在把你自己也烧了吧  Hzoi_chairman
2016-07-11 18:35
5楼
| ||||
|
那时太小不懂事，看见情侣就想烧......
| ||||
|
考试的时候想到了满分的状态居然不会转移QAQ
devil
2015-10-30 08:49
3楼
| ||||
|
树链剖分他妹。。。
 Dissolute丶Tokgo
2015-10-29 21:26
2楼
| ||||
|
前30分秘诀：把f数组的一部分赋为-INF，就可以计算负数了
| ||||
AntiLeaf
Satoshi2062. [ZLXOI 2015][异次元圣战II]燃灵之链
★★★ 输入文件：KPengshuangcang.in
输出文件：KPengshuangcang.out
简单对比时间限制：1 s 内存限制：256 MiB
【题目描述】
战栗吧！丧钟已为你鸣响！
颤抖吧！挽歌已为你宣唱！
末日审判已经降临,
所有情侣都要付出代价！
情侣教会的暴行激起了广大有良知的单身狗的愤怒，一场起义不可避免的爆发了。
单身狗分裂为两派，左派的FFF和右派的SOX。
FFF旨在烧死一切情侣，但是他们缺乏火源。
你作为一名FFF的团员，接受命令寻找传说中的具有火焰魔法能量的燃灵之链。
然而，当你找到燃灵之链时，却发现燃灵之链的一部分受到了恶魔能量的腐蚀，即所谓负能量，
一部分仍然拥有正能量，为了满足K个起义军团的需要，你需要在含有n个能量子的项链中选取K个互不相邻的子项链。
求所能得到的能量的最大值。（相等恶魔能量和正能量可以在数值上抵消）
【输入格式】
第一行，两个正整数n和k
第二行，这条项链从左到右每个能量子的能量值
【输出格式】
一个正整数ans,为最大值
【样例输入】
7 3
5 -1 4 -8 2 -3 5
【样例输出】
15
【提示】
三个子项链分别为(5,-1,4)(2)(5)
首先我们观察得出：
这条链是一个一叉树
其次要对这棵树进行剖分
所以我们自然想到了树链剖分
百度搜索树链剖分，你值得拥有！
对于 20%的数据，N<=20;K<=10;
对于 70%的数据，N<=1000,K<=100;
对于 100%的数据,N<=10000,K<=1000;
能量子的范围为[-2^15,2^15]
【来源】
在此键入。