区间DP之类似树形结构增加限制合并枚举状态：CF1107E
区间dp之类似树形结构增加限制合并枚举状态：CF1107E
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/133759674
https://www.luogu.com.cn/problem/CF1107E
场上想的思路是朴素 ，枚举区间和多少个0/1，转移则是枚举分界点和左边0/1数量
然后可以发现转移的 似乎不那么必要（就是感觉上可以优化，但不知道怎么优化）
首先发现最后合并在一起的东西映射到原序列里是一种类似树形结构的东西。然后可以考虑类似用消掉中间的东西来区间dp
表示 右边还接了 个0/1 的最小价值。枚举分界点还是要的，但是对于0/1，我们每次只考虑一个，也就是 只转移到
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2021-11-14
【UVA10559 方块消除 Blocks】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15552903.html 题目链接 首先先预处理，把连续方块合一，变成 P2135 方块消除。 没错这题是双倍经验 设 dp(i,j,k)dp(i, j, k)dp(i,j,k) 为区间 [i,j][i, j][i,j] 内后面与 a[j]a[j]a[j] 相同颜色的方块有 kkk 个，然后分两种情况考虑。 直接把 [i,j−1][i, j-1][i,j−1] 裁掉，于是 dp(i,j,k)=dp(i,j−1,0)+(b[j]+k)2dp(i,...
2023-12-16
妙妙区间DP（从大往小，计算小对大的贡献（2^n的区间DP））AGC035D
妙妙区间dp（从大往小，计算小对大的贡献（2^n的区间dp））AGC035D 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135028688 https://www.luogu.com.cn/problem/AT_agc035_d 设 f(l,r,fl,fr)f(l,r,fl,fr)f(l,r,fl,fr) 表示现在在区间 [l,r][l,r][l,r] ， al−1+1a_{l-1}+1al−1+1 对答案贡献为 flflfl ， frfrfr 同理。...
2021-11-17
【P2339 [USACO04OPEN]Turning in Homework G】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15570096.html 题目链接 先按作业的提交地点排序。 设 dp(l,r,0/1)dp(l, r, 0/1)dp(l,r,0/1) 为还剩 [l,r][l, r][l,r] 的作业没交，且下一步交 l(0),r(1)l(0), r(1)l(0),r(1) 的最小步数。 显然： dp(l,r,0)=min(max(dp(l−1,r,0)+∣al−1−al∣, tl), max(dp(l,r+1,1)+∣ar+1−al∣, tl))dp(...
2022-01-17
【P1040 [NOIP2003 提高组] 加分二叉树】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15813525.html 题目链接 题目 设一个 nnn 个节点的二叉树 tree\text{tree}tree 的中序遍历为(1,2,3,…,n)(1,2,3,\ldots,n)(1,2,3,…,n)，其中数字 1,2,3,…,n1,2,3,\ldots,n1,2,3,…,n 为节点编号。每个节点都有一个分数（均为正整数），记第 iii 个节点的分数为 did_idi，tree\text{tree}tree 及它的每个子树都有一个加分，任一棵...
2023-12-17
破环成链+运用特殊性质进行区间DP：AGC039E
破环成链+运用特殊性质进行区间dp：AGC039E 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135041477 https://www.luogu.com.cn/problem/AT_agc039_e 数据范围很小，考虑枚举很多东西。 看到环，首先肯定要破环成链，直接令 nnn 连出。考虑现在我们有一个 [1,n−1][1,n-1][1,n−1] 的区间，其中第 kkk 个点往外连了，为了确保联通， [1,k−1],[k+1,n−1][1,k-1],[...
2023-12-16
区间DP（刷表法转移）：P5336
区间dp（刷表法转移）：P5336 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135028996 https://www.luogu.com.cn/problem/P5336 离散化后枚举 g(l,r,mn,mx)g(l,r,mn,mx)g(l,r,mn,mx) ，和 f(l,r)f(l,r)f(l,r) （全删情况），然后考虑使用刷表法来转移。 ar+1a_{r+1}ar+1 加进来，更新 mn,mxmn,mxmn,mx 即可 不加进来，停表...