dp专项训练与题型总结（持续更新）
目录常见题型：（常规模型）
树上dp
区间dp
lis
背包
等等。
经过n次考试的洗礼，我发现我的dp能力太弱了,所以决定来专练一下
刷题1：雷涛的小猫 （我称此类题型为EZ模型）
https://www.luogu.com.cn/problem/P1107
完全没问题，关键注意的是限制条件，一般是满足条件A一种dp，其他另外一种dp
我的错在于：
讨论了A 但是其他的dp忽略了.
总结题型：
这是最简单的，很容易就能设计出dp
直接顺着或者逆着无脑做就行了
刷题2:教主的花园(我称此类题型为影响模型）
https://www.luogu.com.cn/problem/P1133
https://www.luogu.com.cn/record/118038913
我的错在于：
很可惜的是没想到怎么搞定环，这里看了题解的
因为1和n有关系，所以还要多一维存一下第一个选的什么树
还要注意就是初始化（我是复制我前面写的，忘记改初始值了）
经验（变式）
其实是这些题的变式：
变式1: （NOIP模拟赛T1)
http://222.180.160.110:1024/problem/10456
这道题没有题目描述，大致意思就是1维扫雷游戏，给你一个残局，问你把这个残局补充完整的方案数
dp方程式3维,相比这道题而言就是他不是环，以及状态转移稍多了一点。
总体而言应该还简单了一点
就不给出代码了,因为和上一题基本上一模一样
变式2：(cf Array Painting)
洛谷网址：
https://www.luogu.com.cn/problem/CF1849D
原网址：
https://codeforces.com/contest/1849/problem/D
很可惜，这个不是叫你填空了，而是叫你选择其中几个格子涂色
而且呢，每个格子影响的范围可能不一样。
但是这个影响的范围非常有规律：和非0连续段的起点和终点有关系!
然后再仔细思考，这个还是影响连续的三个。
为甚？全是1的连续段可以看成单独1，有2的连续段可以看成单独的2.这两种数字都是影响附近一个或两个0的染色
至于问题的询问方法改变了，只需要将dp改为贪心做就好了、
我的代码：
https://codeforces.com/contest/1849/submission/216233764
总结题型：（影响模型）
仔细看这些题，发现有个共同点：连续的几个个是互相都有影响的，而且，一个数不仅前面可以影响他，后面也可以影响他。
这就让他和一般dp有了一定的区别,因为一般dp没有什么后效性，直接顺着或者逆着无脑做就行了（EZ模型）
例如前面两道题：因此设计了两维，一个表示此位置选什么，另一个表示前一个位置选什么
通过这样表示就能确定三者具体的关系了。
看完最后一个题
那么思维延伸下，出现4个互相有影响的呢？5个呢
加维数肯定是可以完成此类题型的了
但是可以影响的范围不定呢（第三题），那么就要找到决定其影响范围的原因
例如第三题，发现影响范围和连续非0区间有关系。