DP五十题

目录

• 1.合唱队形
  俩遍LIS
• 2.导弹拦截
  nlogn LIS
  某定理：
  Dilworth定理的大概意思：最少的下降序列个数==整个序列最长上升子序列的长度
• 3.尼克的任务
  倒序递推
• 4.丝绸之路
  顺推
• 5.分队问题
• 6.低价购买
  LIS+DP套DP
  在O(n^2)版的LIS的f数组上计数
  
• 7.回文字串
  第二个数组为倒着的串
  对这俩串做一遍LCS
  大胆猜结论：结论：要添加的个数就是len-LCS的长度
• [ 8.模板]最长公共子序列
  映射，转化为求LIS
• 9.魔族密码

• 10.创意吃鱼法
  思路与最大子正方形相似，注意要考虑从左上到右下和右上到左下

• 11.UVA10635 Prince and Princess
• 12.木棍加工
• [ 13.USACO08MAR]跨河River Crossing
• 14.UVA11400 Lighting System Design
• 15.出租车拼车
• 16.最佳课题选择
• [ 17.USACO06FEB]奶牛零食Treats for the Cows
• 18.能量项链
• 19.跳房子
• 20.摆花
• 21.HDU5115
• [ 22.USACO13NOV]POGO的牛Pogo-Cow
• 23.乌龟棋
• [ 24.USACO08JAN]跑步Running
• 25.过河
• [ 26.USACO07FEB]牛的词汇The Cow Lexicon
• [ 27.USACO07MAR]牛交通Cow Traffic
• [28.USACO07NOV]挤奶的时间Milking Time
• 29.装箱问题
• [30.HNOI2004]打鼹鼠
• 31.道路游戏
• [32.CQOI2007]涂色
• [ 33.BeijingWc2008]雷涛的小猫
• 34.教主的花园
• 35.烹调方案
• 36.经营与开发
• 37.货币系统
• [ 38.HAOI2012]音量调节
• 39.机器分配
• 40.花店橱窗布置
• 41.看球泡妹子
• 42.选学霸
• 43.字串距离
• 44.传球游戏
• 45.积木城堡
• 46.字符串折叠
• 47.UVA1025 A Spy in the Metro
• 48.传纸条
• 49.书本整理

• 50.Zjoi2004]Lunch 午餐

DP五十题

原文：https://www.cnblogs.com/sjsjsj-minus-Si/p/11657214.html