文和906

题解

未归档(4) 项目笔记(5)

/ 注册

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

题解 | #合并回文子串#

区间DP问题。与涂色问题大同小异，但如果想不明白就会觉得这两者有很大区别。用一个四维数组dp[l1][r1][l2][r2]表示从第一个字符串中取l1到r1，从第二个字符串中取l2到r2是否能组成回文字符串，若不能则为0，能则为1。状态转移方程分4种情况，因为字符串Ａ、Ｂ有四种情况可以组成会问字符串...

C++ 区间dp 动态规划

2021-11-03

0 580

题解 | #[CQOI2007]涂色PAINT#

区间dp。我也对这类题型比较陌生，只能写下自己浅薄的理解，欢迎大佬指教。开始时对这道题没什么头绪，查阅了一些资料后写下了这段程序。不敢说已经完全理解，只记录下我写代码时的思路。这里dp数组记录的是将第i个位置到第j个位置涂色的最少次数。初始化dp时，由于是求最小值，所以先将数组中所有元素初始化为一个...

C++ 动态规划区间dp

2021-11-02

2 680