shyyhs

题解

DP专题(52) 图论(4) 多校补题(2) 数据结构(27) 数论(4) 日记(14) 未归档(38)

/ 注册

全部文章 / 题解（共57篇）

进来DP 来自专栏

大部分代码贪心解法是错误的,原题是CF1442D,可以在cf上测试一下. 首先不考虑贪心,这是个分组背包O(N2K)O(N^2K)O(N2K),考虑贪心暴力仍然是O(N2K)O(N^2K)O(N2K). 贪心题解讲的很清楚了,那么我们如何能够做到更优的时间复杂度解决这个问题呢. 可以是分治,在每次递...

dp

2022-04-04

0 461

★★飞马祝福语★★ 来自专栏

为什么要写这个题的题解呢? 因为我觉得很可惜...尽管我做过类似的,类似这题 ,知道是线段树上分治跑dp,但是因为只做过一次,不敢写,因为怕bug然后调不出,事实上我又调了很久,确实菜,但是呢必须得说下次我绝对敢写. 这种题是基于线段树本身带有分治结构,对于每段来说就是先算段内贡献,然后算段外的贡献...

线段树 dp

2021-05-30

3 684

[HAOI2015]树上染色来自专栏

思路转移什么按边计算都是套路...小菜鸡每次接触边界问题就死翘翘啦.这题的第二维必须枚举,或者你提前算的贡献,因为你一直在想要不要重复的问题,所以你第一维肯定正序,但是注意当你时,本来就已经更新过了,已经不是这个值了,现在你又更新一次,这里就存在重复了.对于其他也没什么好讲的...我竟然上课理解这...

dp

2021-03-18

2 838

[HNOI2004]打鼹鼠来自专栏

和最近的一个出的题很像,都是倒着这样的. 思路不妨设表示为消灭了节点的鼠,并且在节点所能获得的最大收益是多少.很显然的方程: . 这样这个问题就解决了. 代码 #include <bits/stdc++.h> using namespace std; const int N=1e4+5...

dp

2021-03-15

4 863

[HAOI2016]字符合并来自专栏

思路可能是个套路题,但是没见过...第一眼觉得是个区间,但是中间的状态总是弄不清楚...然后看了题解是状压+区间.令表示为区间合并成字符串所获得的最大代价.区间的划分有个优化就是,每次只能是这种才能形成,然后就行划分,当区间是这个长度的时候进行一次答案统计即可. 代码 #include <b...

dp

2021-03-11

2 925

石子搬运来自专栏

思路我线段树属于那种看到题解一般能懂,自己有时候想不到的层次...这题应该就是一个线段树...单纯的已知次数下搬运石头肯定是平方答案最优.然后假如不含修改的话,就是一个超级简单的.假如含有修改呢...我们不妨把它放到线段树上进行.令表示为到了这个石头堆(因为线段树是一群一群石头进行维护的嘛~)选了...

线段树 dp

2021-03-11

0 970

选课来自专栏

前言清楚姐姐树形题单的最后一题了... 思路考虑先当前节点必须把当前节点前面连接到根的节点全部选了..那么我们不妨令为选了节点且选取数量为的一个最大价值.那么转移似乎挺简单的. 代码 #include <bits/stdc++.h> using namespace std; cons...

dp

2021-03-10

2 623

Full Depth Morning Show 来自专栏

前言我觉得只要给我时间到这题就随便过,因为我对于换根还是没那么熟悉...读这题的时候就半小时了,知道写不完了,就没写了..今天写了,debug也差不多..我代码真的容易出bug...下次一定提前开题,签到题留给队友写.感觉就是cf2100到2200的换根dp. 思路好像就是一些式子推一下,首先算...

dp

2021-03-08

3 718

[JSOI2009]等差数列来自专栏

思路对于这题,首先要知道维护一些什么东西.我们都知道区间加个等差数列,假如维护单点求和的话,直接维护公差即可.因为区间加一个等差数列只需要两次单点修改和一次区间修改即可.对于这题,我们很容易想到维护公差.但是对于查询操作维护公差是远远不够的.每次是询问你区间中有多少个等差数列.对于这个查询啊,我们...

线段树 dp

2021-03-08

4 1137

蓝魔法师来自专栏

思路思路应该算是比较简单吧...难点在于时间复杂度的证明.因为这题和的范围都是以内的.题目是让你切成若干份,每份大小都不超过,因为是一棵树,所以很容易想到树形.对于树形,我们很容易想到利用子树就行转移.那么我们要转移什么,才能让子树来跟新父节点呢?很显然的一个东西,我可以和子树分割,也可以不和子树...

dp

2021-03-05

2 938