动态规划-基础篇

wflengxuenong · 2023-11-09 17:29:51 · 个人记录

动态规划的引入

• 0动态规划和贪心

• P1809 过河问题

• 1.1 数字三角形模型

  • P1216 [USACO1.5] [IOI1994]数字三角形 Number Triangles
  • P1130 红牌
  • P1002 [NOIP2002 普及组] 过河卒
  • P8707 [蓝桥杯 2020 省 AB1] 走方格

• 1.2 如何定义阶段？

  • P1434 [SHOI2002] 滑雪

  高度是本题转移的特点。以高度来划分阶段。

  • P7074 [CSP-J2020] 方格取数

  一个状态既可以由上方来，也可以由下方来，单纯的右下方向阶段划分已经不够用了。由于不走充分的格子，上下两个方向是独立的，可以多设计一维状态。

  • P1006 [NOIP2008 提高组] 传纸条
  • T392580 palin
  • T385929 跳格子游戏

• 1.3 上升子序列模型

  • B3637 最长上升子序列

  • P2008 大朋友的数字

  • AT_chokudai_S001_h LIS

  • P1091 [NOIP2004 提高组] 合唱队形

  • P8697 [蓝桥杯 2019 国 C] 最长子序列

  • P2782 友好城市

  • T390216 谁共一杯芳酒

  • P1439 【模板】最长公共子序列

  • 1.4 子段和问题

  • P1115 最大子段和

  • AT_arc137_b [ARC137B] Count 1's

  • P1121 环状最大两段子段和

  • P1387 最大正方形

• 1.5区间型动态规划

• P1880 [NOI1995] 石子合并

• P1040 [NOIP2003 提高组] 加分二叉树

• P1063 [NOIP2006 提高组] 能量项链 AT_dp_l Deque

• P2654 原核生物培养

• P1005 [NOIP2007 提高组] 矩阵取数游戏

• P1220 关路灯

• P4170 [CQOI2007] 涂色

• P4767 [IOI2000] 邮局

• P3146 [USACO16OPEN] 248 G

• P3147 [USACO16OPEN] 262144 P

• P3205 [HNOI2010] 合唱队

• 1.6 背包问题

  • B3635 硬币问题

  • P8742 [蓝桥杯 2021 省 AB] 砝码称重

  • P2722 [USACO3.1] 总分 Score Inflation

  • P1877 [HAOI2012] 音量调节

  • P1679 神奇的四次方数

  • P1649 [USACO07OCT] Obstacle Course S

  • P6208 [USACO06OCT] Cow Pie Treasures G

  • P1970 [NOIP2013 提高组] 花匠

• P2896 [USACO08FEB] Eating Together S

• P2858 [USACO06FEB] Treats for the Cows G/S

• P1192 台阶问题

• P1020 [NOIP1999 普及组] 导弹拦截

• P1280 尼克的任务

• P1944 最长括号匹配

• P4310 绝世好题

• P1048 [NOIP2005 普及组] 采药

• P1616 疯狂的采药

• P1064 [NOIP2006 提高组] 金明的预算方案

• P1776 宝物筛选

• P5020 [NOIP2018 提高组] 货币系统

• P5322 [BJOI2019] 排兵布阵

• P1025 [NOIP2001 提高组] 数的划分

• P1140 相似基因

• P1233 木棍加工

• P1941 [NOIP2014 提高组] 飞扬的小鸟

• P4170 [CQOI2007] 涂色