# DP優化
<!--
## info
DP是用小的DP轉移到大的DP
而這個過程會有轉移式
我們可以用一些方法優化轉移式推進的過程
-->

## 矩陣快速冪優化
### 先備知識
[快速冪&矩陣快速冪](/f6LDVf4yTNy-b4vf7kbx9g)

### 轉移式換成矩陣
轉移式中一種常見的形式就是遞迴式
而我們可以將遞迴式換成矩陣乘法
不過單純改成用矩陣乘法轉移並不會減少複雜度
所以我們要在矩陣乘法上加上快速冪

我們舉一個簡單的例子，費式數列
費式數列的轉移式
$f_n = f_{n-1} + f_{n-2}$
可以換成
$$
\left[
\begin{array}{1}
f_n \\
f_{n-1}
\end{array}
\right]=
\left[
\begin{array}{1}
1 & 1 \\
1 & 0
\end{array}
\right]
\left[
\begin{array}{1}
f_{n-1} \\
f_{n-2}
\end{array}
\right]
$$
所以
$$
\left[
\begin{array}{1}
f_{n+1} \\
f_{n}
\end{array}
\right]=
\left[
\begin{array}{1}
1 & 1 \\
1 & 0
\end{array}
\right]^{n}
\left[
\begin{array}{1}
f_1 \\
f_0
\end{array}
\right]
$$

### 優化
列出這個式子我們可以發現如果我們把n次方用矩陣快速密來處理就可以用$O(logn)$的時間計算

### 例題
[TIOJ 2053](https://tioj.ck.tp.edu.tw/problems/2053)
[UVA 10870](https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=489&page=show_problem&problem=1811)

### 題解
:::info
:::spoiler TIOJ 2053題解
:::warning
這題的遞迴式是$X_n = bX_{n-1} + aX_{n-2}$
已知
$$
\left[
\begin{array}{1}
X_n \\
X_{n-1}
\end{array}
\right]=
\left[
\begin{array}{1}
b & a \\
1 & 0
\end{array}
\right]
\left[
\begin{array}{1}
X_{n-1} \\
X_{n-2}
\end{array}
\right]
$$
可知
$$
\left[
\begin{array}{1}
X_{n+1} \\
X_{n}
\end{array}
\right]=
\left[
\begin{array}{1}
b & a \\
1 & 0
\end{array}
\right]^{n}
\left[
\begin{array}{1}
X_1 \\
X_0
\end{array}
\right]
$$
得出了這個式子
接下來就只要用矩陣快速冪答案就出來了
:::

:::info
:::spoiler UVA 10870題解
:::warning
$f(n) = a_1 f(n - 1) + a_2 f(n - 2) + a_3 f(n - 3) + ... + a_d f(n - d) , (n > d)$
已知前d項求第n項
這題可以將f(n)的式子列成矩陣，並用矩陣快速冪的方式快速取值

$$
\begin{bmatrix}
f(n) \\
f(n- 1) \\
f(n -2) \\
\vdots \\
f(n-d+1)
\end{bmatrix}=
\begin{bmatrix}
a_1 & a_2 & a_3 & \cdots & a_{d-1} & a_d\\
1 & 0 & 0 & \cdots & 0 & 0 \\
0 & 1 & 0 & \cdots & 0 & 0\\
\vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\
0 & 0 & 0 & \cdots & 1 & 0 \\
0 & 0 & 0 & \cdots & 0 & 0
\end{bmatrix}
\begin{bmatrix}
f(n-1) \\
f(n- 2) \\
f(n -3) \\
\vdots \\
f(n-d)
\end{bmatrix}
$$
:::

## 資料結構優化

在一些DP轉移式中會出現區間查詢
例如
$DP[i+1] = v[i] + max(DP[i-k] 到DP[i])$
(假設DP轉移長度為n)
一般我們可能會用for迴圈一個一個跑過找到最大值要花O(k)
總複雜度就會是O(nk)
但如果運用[線段樹](/9WMgzFs6RbCZ3LQ5NSf7QQ)或[BIT](/fH6_FqTnQb2BHEV6EhG3lQ)就可以將區間查詢的部分變成O(logko
總複雜度就會是O(nlogk)

這個很少用而且code很常我就不放的
## 單調隊列優化
在學習單掉隊列如何優化DP前先學一下什麼是單調隊列吧
[單掉隊列](/_VjchRMtRSyTgMyBQmB8QA)
學完單調對列我們就可以優化剛剛這種這種固定區間查詢大小和相對位置的dp了
$dp[i] = val[i] + max(dp[i - k] 到 dp[i])$
單調和dp更新同時進行
時間複雜度$O(n)$

[例題](https://neoj.sprout.tw/problem/188/)
轉移式:
$dp[i] = val[i] + max(dp[i - k] 到 dp[i]) - 間隔數量 * c$

#include<bits/stdc++.h>
using namespace std;
#define int long long

signed main(){
    int t;
    cin >> t;
    while(t--){
        int n, k , c;
        cin >> n >> k >> c;
        int val[n];
        for(int i = 0; i < n; i++){
            cin >> val[i];
        }
        int dp[n];
        dp[0] = val[0];
        deque<int> dq;
        for(int i = 0; i < n - 1; i++){
            while(!dq.empty() and dq.front() <= i - k){dq.pop_front();}
            while(!dq.empty() and dp[dq.back()] + dq.back() * c <= dp[i] + i * c){dq.pop_back();}
            dq.push_back(i);
            
            dp[i+1] = val[i+1] + max(0LL,dp[dq.front()] - (i+1 - dq.front()) * c);
        }
        int ans = 0;
        for(int i = 0; i < n; i++){
            ans = max(ans, dp[i]);
        }
        cout << ans << '\n';
    }
    
}