iceylemon 的程式小空間
  • iceylemon 的程式小空間
  • 小知識
    • 施工中的筆記
      • Tree
        • 重心剖分
    • Dynamic Programming
      • DP Time
        • 暖身題單
        • LIS と LCS
        • 二維 DP
        • 背包 DP
        • 區間DP
        • 環狀DP
        • 狀壓DP
        • 樹DP
        • 數位DP
      • DP OPT Time
        • 前綴和優化
        • 矩陣快速冪優化
        • 資料結構優化
        • SOS 優化
        • 單調隊列優化
        • 斜率優化 (Convex Hull Trick)
        • 四邊形優化
        • Aliens 優化
        • Slope Trick
  • 隨筆
    • 題解
      • CF 1557D
Powered by GitBook
On this page
  • 介紹
  • 例題

Was this helpful?

  1. 小知識
  2. Dynamic Programming
  3. DP Time

區間DP

施工中

Previous背包 DPNext環狀DP

Last updated 3 years ago

Was this helpful?

介紹

在區間上做DP，通常複雜度都是 N2,N3N^2,N^3N2,N3 有時候可以搭配莫名其妙的四邊形優化。

用遞迴寫會異常好寫

例題

先來些經典題

  1. 最經典題，但是要搭配斷環成鍊(也就是複製然後接兩倍)

再來一些比較難一點點的題目

  2. 特殊的轉移方式

石子合併
n個矩陣相乘最少次數
最優三角剖分
105全國賽 pD
105全國賽pD變化
CF149D
[IOI1998] Polygon
2020 ICPC Asia Taipei-Hsinchu Regional pE
Blocks