# dp 優化 --- ## 回顧一下dp在做什麼 把大問題切成(會重複用到的)子問題 狀態和轉移 ---- ## 先講一些上次沒講的技巧 ---- ## [置換](https://atcoder.jp/contests/dp/tasks/dp_t) ---- 發現到一個$[1,n]$的置換其實可以看成已經有一個$[1,n+1]$的接著在最後面$+$一個$x$最後在把前面$\geq x$的都$+1$。 ---- 把$dp[i][j]$設成前面有$[1,i]$的置換，最後一項是$j$的個數。 轉移就好好看大小 ---- ## [開關區間](https://cses.fi/problemset/task/1665) ---- 發現到貢獻需要知道的只有每個人是不是最大或最小的 由大到小加進來 $dp[i][j][k]$是看了最大的$i$個人現在有$j$個人當最大值而且他們還沒有配到最小值，$k$是現在的貢獻的個數 --- ## dp優化想做什麼 在一些有著好性質的dp 我們利用好性質去偷懶 ---- ## 最簡單的例子 greedy ---- ## 單調隊列優化 ---- ## sliding window 長為$n$的數列$a_i$，問每個長為$k$的區間裡的最大值。 單調隊列。 好事情：轉移的範圍幾乎沒有變。 ---- ## 有限個數多重背包 有$n$種物品，每個物品有重量$w_i$價值$v_i$個數$a_i$，背包承重$W$。 ---- 合併物品變01背包 $O(W\sum\log(a_i))$ ---- 狀態和01背包一樣 轉移：$dp_{i,j}=\displaystyle\max_{0\leq x\leq a_i}(dp_{i-1,j-xw_i}+xv_i)$= 對$j$ mod $w_i$ 做sliding window ---- ## 題目 - [題](https://codeforces.com/problemset/problem/372/C) --- ## 矩陣 算費氏數列第$i$項模$p$ 發現到 $\begin{pmatrix}0 & 1\\ 1& 1 \end{pmatrix}\begin{pmatrix}F_i \\F_{i+1} \end{pmatrix}=\begin{pmatrix}F_{i+1} \\F_{i+2} \end{pmatrix}$ 矩陣有結合率 那我們就可以做快速冪 ---- 記得矩陣的運算可以亂改(我們只有用到結合率) ---- [沒吃毒](https://slides.com/becaido/dp-op#/3/7/0) [吃毒](https://slides.com/becaido/dp-op#/3/10/0) --- ## 斜率優化 [偷偷偷](https://slides.com/becaido/dp-op#/2) ---- ## 優超性 我們說 $f$ 優超 $g$ 如果 $\exists p$ 使得 $f(x)>g(x)\,\forall x<p$ $f(x)\leq g(x)\,\forall x\geq p$ ---- ## 1d/1d $dp_j=\displaystyle\min_{0\leq i<j}\{f(i,j,dp_i)\}=\min_{0\leq i<j}\{f_i(j)\}$ 如果有$f_i$優超$f_j\,\forall i<j$我們說他是凹單調的 如果有$f_i$優超$f_j\,\forall i>j$我們說他是凸單調的 ---- 發現到他基本上就是斜率優化 可以用李超 但詢問單調而且贏的方向單調 所以能用deque去維護(在凹的時候可以只用stack) 在判交點的時候要二分搜 ---- ## monge $f_i(j)+f_{i+1}(j+1)\geq f_i(j+1)+f_{i+1}(j)$的話 他就是凸單調 反過來就凹 monge比單調性還要緊，所以不能從單調推monge ---- ## 題目 - [黑白機](https://tioj.ck.tp.edu.tw/problems/2231) - [偶像選拔祭](https://tioj.ck.tp.edu.tw/problems/2328) - [暴雷](https://oj.uz/problem/view/APIO24_train) --- ## [knuth](https://cp-algorithms.com/dynamic_programming/knuth-optimization.html) [例題](https://cses.fi/problemset/task/2088) 設$[l,r]$被切在$opt(l,r)$ $opt(l,r)\leq opt(l,r+1)\leq opt(l+1,r+1)$ 以長度大小掃 每個長度只要掃$O(n)$ 總共$O(n^2)$ --- ## 轉移點單調 現在在做1d/1d，我們有的只有最佳轉移點會遞增 ---- ## 費用可以離線 做分治 假設divide(x,y,l,r)能做完$[x,y]$轉到$[l,r]$ 花$O(y-x)$能找到中點m的最佳轉移點是opt 那要再做divide(x,opt,l,m-1), divide(opt,y,m+1,r) 複雜度分析和knuth差不多 ---- ## 現在要在線了 [cdq](https://oi-wiki.org/misc/cdq-divide/): 做完$[l,m]$ 拿$[l,m]$去轉$[m+1,r]$ 做$[m+1,r]$ --- ## slope trick [偷](https://codeforces.com/blog/entry/77298) 左邊是$y=ax+b$經過一個$+1$斜率的點$p$會變 $y=(a+1)x+(b-p)$ --- ## aliens [8e7好強](https://slides.com/justinlai2003/dp-dp#/7) ---- ## 題目 - [aliens](https://tioj.ck.tp.edu.tw/problems/1961) - [暴雷](https://oj.uz/problem/view/JOI23_chorus)