DP入门练手题

题单即将更新成五个部分 ---- DP的经典好题。 LIS，LCS，背包等经典模型都有加强版应用。 有CF的题目，思维难度较大。 状压DP仅一道，属于TSP问题的模板题（当然SA可以过%%%） 练完应该可以熟练基本的DP。 说实话……黄题我是真心不想收录（太水），但是收录的一定很经典。 ----- 这里给出各种类型的题目整理： 线性DP： - [P3842 [TJOI2007]线段](https://www.luogu.com.cn/problem/P3842) - [CF698A Vacations](https://www.luogu.com.cn/problem/CF698A) - [CF191A Dynasty Puzzles](https://www.luogu.com.cn/problem/CF191A) - [CF358D Dima and Hares](https://www.luogu.com.cn/problem/CF358D) - [CF176B Word Cut](https://www.luogu.com.cn/problem/CF176B) - [CF4D Mysterious Present](https://www.luogu.com.cn/problem/CF4D) - [CF706C Hard problem](https://www.luogu.com.cn/problem/CF706C) - [CF713C Sonya and Problem Wihtout a Legend](https://www.luogu.com.cn/problem/CF713C) - [CF687C The Values You Can Make](https://www.luogu.com.cn/problem/CF687C) - [P1799 数列](https://www.luogu.com.cn/problem/P1799) - [P1020 导弹拦截](https://www.luogu.com.cn/problem/P1020) - [P1439 【模板】最长公共子序列](https://www.luogu.com.cn/problem/P1439) - [P1280 尼克的任务](https://www.luogu.com.cn/problem/P1280) - [P1140 相似基因](https://www.luogu.com.cn/problem/P1140) - [P1052 过河](https://www.luogu.com.cn/problem/P1052) - [P2577 [ZJOI2004]午餐](https://www.luogu.com.cn/problem/P2577) - [P1136 迎接仪式](https://www.luogu.com.cn/problem/P1136) - [P2642 双子序列最大和](https://www.luogu.com.cn/problem/P2642) - [P3902 递增](https://www.luogu.com.cn/problem/P3902) - [P3399 丝绸之路](https://www.luogu.com.cn/problem/P3399) - [P1216 [USACO1.5][IOI1994]数字三角形 Number Triangles](https://www.luogu.com.cn/problem/P1216) - [CF571B Minimization](https://www.luogu.com.cn/problem/CF571B) - [CF269B Greenhouse Effect](https://www.luogu.com.cn/problem/CF269B) 背包DP： - [CF366C Dima and Salad](https://www.luogu.com.cn/problem/CF366C) - [P1616 疯狂的采药](https://www.luogu.com.cn/problem/P1616) - [P1064 金明的预算方案](https://www.luogu.com.cn/problem/P1064) - [P1833 樱花](https://www.luogu.com.cn/problem/P1833) - [P1776 宝物筛选](https://www.luogu.com.cn/problem/P1776) - [CF294B Shaass and Bookshelf](https://www.luogu.com.cn/problem/CF294B) 区间，划分DP： - [CF467C George and Job](https://www.luogu.com.cn/problem/CF467C) - [P1002 过河卒](https://www.luogu.com.cn/problem/P1002) - [P1464 Function](https://www.luogu.com.cn/problem/P1464) - [P2642 双子序列最大和](https://www.luogu.com.cn/problem/P2642) - [P1040 加分二叉树](https://www.luogu.com.cn/problem/P1040) - [P1387 最大正方形](https://www.luogu.com.cn/problem/P1387) - [P1020 导弹拦截](https://www.luogu.com.cn/problem/P1020) - [P1220 关路灯 ](https://www.luogu.com.cn/problem/P1220) - [P1006 传纸条](https://www.luogu.com.cn/problem/P1006) - [P1063 能量项链](https://www.luogu.com.cn/problem/P1063) - [P1880 [NOI1995]石子合并](https://www.luogu.com.cn/problem/P1880) - [P1018 乘积最大](https://www.luogu.com.cn/problem/P1018) 状压DP： - [P1433 吃奶酪](https://www.luogu.com.cn/problem/P1433)