cheese_case

题解

dp题解(2)

/ 注册

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

题解 | #小辰的智慧树#

重点就是发现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 482

题解 | #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

题解 | #进制#

感觉挺不错的一道线段树题目首先考虑区间里面存什么，因为每次修改区间不同进制的值都会跟着改变，最大值也会改变，故要保存所有区间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

题解 | #黑白树#

这题容易想到要从下向上贪心，因为从一个点开始只能染色其以及其上方的一些点，而其下方的点需要额外考虑染色，故而从叶子节点开始考虑染色，叶子节点必须染色其范围是k[i],但是并不是最上面一个点才继续染色，而是当前染色点所包含所有点染色后这些点所能达到的最远距离，如果还需要染色，则染可以更新最远距离相对...

2022-03-10

1 476

题解 | #筑巢#

这题有个小坑，很荣幸踩了进去就是ans得初始化必须是-inf ，各位可能会习惯性初始化为0 思路就是只有子点与相连边的和>0就选择它，反之不选，一个假冒伪劣的树形dp 因为建立树时写成了v[b].push_back[b]导致查不出错误，下次直接把头剁了 #include<bits...

2022-03-05

5 452