cheese_case

分类

dp题解(2) 题解(25)

/ 注册

全部文章（共26篇）

题解 | #小辰的智慧树#

重点就是发现x*(hi*2-x)的最优解相当于每次取最大的hi砍x=1长度，易转化为区间加法问题 #include<bits/stdc++.h> #define int long long using namespace std; typedef long long ll; const ...

2023-11-17

3 569

题解 | #Mate in 33#F IUPC

题意: n个数有t时间每个时间可以选择一个合法的数（每个数只能选择一次），连续k个时间最多选m个，问有多少种方法数思路：想到区间k状态必须要2^k表示对于t 300 ，剩余只有10+的空间给n，思考每次可以选择前缀所有，故每次可以可能可以选多个看前一状态，若前一个状态选到j个那这个可以选到n...

2023-08-18

1 505

题解 | #IUPC

题意: n个数有t时间每个时间可以选择一个合法的数（每个数只能选择一次），连续k个时间最多选m个，问有多少种方法数思路：想到区间k状态必须要2^k表示对于t 300 ，剩余只有10+的空间给n，思考每次可以选择前缀所有，故每次可以可能可以选多个看前一状态，若前一个状态选到j个那这个可以选到n...

2023-08-18

0 526

题解 | #Qu'est-ce Que C'est?#

迫于大佬威压来写题解，J比较明显的状态设计发现区间加法直接上差分即可 #include<bits/stdc++.h> #define int long long using namespace std; typedef long long ll; const int N = 5010...

2023-07-30

3 334

题解 | #小d和送外卖#

一道典型的树形背包，看到n，k值 m<=50 果断用m做完背包第2维，就是选不选的普遍问题了 dp[i][j]：以节点i为根节点子树中没选j个点情况下的最短路径，相当于用了一个滚动数组优化了一个维度下面直接上代码，里面有过程注释 #include<bits/stdc++.h> #...

2023-04-25

3 459

F.小d和送外卖

一道典型的树形背包，看到n，k值 m<=50 果断用m做完背包第2维，就是选不选的普遍问题了 **dp[i][j]：**以节点i为根节点子树中没选j个点情况下的最短路径，相当于用了一个滚动数组优化了一个维度下面直接上代码，里面有过程注释 #include<bits/stdc++.h&g...

2023-04-25

0 229

F.小d和送外卖

链接一道典型的树形背包，看到n，k值 m<=50 果断用m做完背包第2维，就是选不选的普遍问题了 **dp[i][j]：**以节点i为根节点子树中没选j个点情况下的最短路径，相当于用了一个滚动数组优化了一个维度下面直接上代码，里面有过程注释 #include<bits/stdc++....

2023-04-25

0 266

题解 | #进制#

感觉挺不错的一道线段树题目首先考虑区间里面存什么，因为每次修改区间不同进制的值都会跟着改变，最大值也会改变，故要保存所有区间2-10进制所有进制的区间和，合并区间时只需要将左区间*ksm(jin,lenright)即可，思路相对清晰线段树的题目，只需要考虑区间维护什么，且如何合并

2022-04-12

0 292

题解 | # [HAOI2015]树上染色#

感觉是时候总结一下树形背包的题目了，虽然都是树形背包，但是不同题目细节却有着不小的区别，这里我由两道题来分析不同点（尤其是状态是否合法的考虑以及转移循环的范围限制，对于dp 范围的限制一直都算是一个细节考虑），一题是本题，还有一题是经典树上背包 ————选课先上选课 https://www.luo...

2022-04-02

0 445

题解 | #区间价值#

看到还没有题解，那就来一发相对于说这题是dp，我觉得更像是体现了数组预处理信息的一种递推，很巧妙的运用数组储存信息由数据范围知肯定要提前预处理，时间复杂度为O(n),那么容易想到每个区间存在关联，比如f[4]比f[3]多了一个数，贡献在于f[3]中是否有此多出的数，转化一下问题 f【4】新增的...

2022-03-21

3 415