Cwyy

分类

学习笔记(3) 比赛(1) 题解(24)

/ 注册

全部文章（共9篇）

DP浅谈

浅谈由于窝太菜了，只好写这篇浅谈来聊以***。那么我们从最简单的入门开始吧【一】基础一个最基础的入门题。状态：表示到的长度转移：答案统计：因为我们在更新时要找到最大的来更新答案使得答案最优。这样的复杂度是但是我们可以在的时间内完成，此时可以用树状数组来维护。这里来讲...

动态规划

2020-03-07

2 830

题解 CF722E 【Research Rover】

题解- CF722E 题目意思题目就是让你从走到的道路中有个特殊点，没经过一个特殊点会使分数变为原来一半，问从到的期望得分（对取模）我们首先把也看成特殊点，但是分数不用除二，然后为了保证每次是向下或向右先对排序即可，接下来就是啦。这道题目如果把状态设为表示到点经过个特殊点的方...

期望贪心动态规划转化

2020-02-26

1 832

题解 P3523 【[POI2011]DYN-Dynamite】

题解- P3523 DYN-Dynamite 题目意思就是在一颗树中选个点使得这个点到关键点的距离最大值最小。双倍经验总算看懂题解来重新理解一遍，加深记忆。。回归正题，因为题目要我们求最大值最小显然会想到二分。首先我们设几个变量：表示以为子树最近选择节点的距...

二分贪心动态规划

2020-02-25

1 792

题解 P2569 【[SCOI2010]股票交易】

题解- P2569 股票交易题目意思由于题面过长，不再描述。戳这里这道题目想清楚后还是不难的，是一道不错的单调队列练习题。首先我们要明确状态：表式到第天拥有个股票的最大收益。这个状态还是挺显然的，不像某些题目卡状态。对于转移，要分成多种情况来考虑： ...

单调队列动态规划

2020-02-16

1 713

题解 CF264C 【Choosing Balls】

题解- CF246C Choosing Balls 题目意思说人话就是你可以选若干个物品，若这次选择的物品与上次选的相同那么这个的贡献就是否则是。要使得利益最大化。一开始我以为是什么贪心。后来想想认为还是一个。就是要利用其特殊的一个性质单调性我们设表示到现在选择的最后一个元素...

动态规划转化

2020-02-06

1 711

题解 P6040 课后期末考试滑溜滑溜补习班

题解-P6040 「ACOI2020」课后期末考试滑溜滑溜补习班题目意思题目较长，不便于描述这道题目就是考察了一道基础的单调队列优化，以及化柿子的方法。，暴力设表示到的最小花费精力，转移即可 if(n<=1000) { memset(f,127/3,si...

单调队列动态规划转化

2020-02-01

1 674

题解 P6005 Time is Mooney G

题解-P6005 Time is Mooney G 题目意思就是给你一个有向图，你在上面走，没经过一个点可以获得，最后你要减去(走过的边数) 考虑,我们设表示第天到达城市的最大收益。转移很简单对于的处理我们只需要反向建有向边即可，答案就是但是这样的枚举范围无法确定，但是我们发现即可，因...

最短路动态规划转化

2020-01-26

1 1078

题解 P1156 【垃圾陷阱】

这是一道很好的题目对于这道题目，我们首先明确的状态：表示当扔下第个垃圾时，高度为此时的还可以存活多久对于转移，我们要分两种情况：当不选用这个垃圾来当垫子时：当选用这个垃圾来当垫子时表示垃圾可以垫高的高度表示吃垃圾可以维持的生命多少对于爬不出的情况：初始化： #include...

贪心动态规划

2019-10-15

1 768

题解 P1850 【换教室】

题解- NOIPDay1T3 换教室题目意思题面很长但是挺好懂的。就是你有次换课机会从班级转换到班级，但是只有的概率能够成功转换，代价就是到的最短路。问你期望总和最小是多少？主要用到的算法为最短路以及动态规划最短路就是求出任意两个点之间存在的最短路距离，用就可以求解，所以能过的 ...

期望最短路动态规划

2019-10-15

1 474