Absoler

动态规划

Java开发(1) MFC(1) 图论(7) 基本算法(6) 字符串(3) 思维(2) 搜索(7) 数学(2) 数据结构(4) 未归档(29) 杂项(1) 树(2) 模板(3) 真题(9) 计算几何(1)

/ 注册

全部文章 / 动态规划（共4篇）

NC20663 dp 来自专栏

这题数据还是有点水啊，，四重循环过了。看到有大佬做了优化不过暂时没研究。关键步骤是想到我们按列划分子状态，每处理一个子三角后可以在它右边“贴上”一列技能点，贴上的边不能长于原三角右侧边长度+1，我们用dp[i][j][k]表示从左至右的第i列选了j个技能，总使用技能点数k情况下的最大收益，就可以写出...

每日一题 dp

2020-08-25

1 675

NC20252 区间dp 来自专栏

https://ac.nowcoder.com/acm/problem/20252 字符串最长50，求压缩后的最短长度。这题的关键在于M。如果只有R，那么就是基础的区间dp，每次可以压缩时令dp(l,r) = min(dp(l,r), dp(l,mid)+1)，三重循环搞定。多出了规定“M”改变...

每日一题区间dp

2020-07-13

0 790

NC19810（dp）来自专栏

https://ac.nowcoder.com/acm/problem/19810这题有个结论比较好猜……题目大意是，给定n要求构造一棵权值最大的树，如果一个点是父亲的重儿子，那么权值等于父亲，否则等于父亲权值+1，根权值=0。设i个节点的树的最大权值是dp[i]，然后当我们想构造一棵大小为n的树时...

每日一题

2020-07-10

0 688

NC16645（基础区间dp+高精度）来自专栏

https://ac.nowcoder.com/acm/problem/16645 这道题唯一需要注意的就是高精度了吧……思路很简单，首先发现可以每行单独处理，用dp[l,r]表示选择lr区间内的最大收益，有公式然后就在n2内处理一行，n3处理整个矩阵即可。值得一提的是高精度__int128不能在...

每日一题

2020-07-09

0 703