# 動態規劃
---
## 核心概念：
## 將問題分成子問題重複利用
- 定義dp狀態（無切入點可增加維度）
- 列出轉移式（依需求調整定義）
- 初始化邊界條件
----
## [IOI1994 -- 数字三角形](https://www.luogu.com.cn/problem/P1216)
給定一個 $1\leq n\leq1000$ 層的數字金字塔，第 $i$ 層共有 $i$ 個數字，從金字塔頂部開始，每次可往左下或右下走，直到最下層，求路徑數字和最大值
----
- 設 $dp[i][j]$ 為從座標 $(i,j)$ 往下走的最大值
- $dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+ar[i][j]$
- $dp[n][j]=ar[n][j]$
- $ans=dp[1][1]$
----
程式碼：
```cpp!
#include <bits/stdc++.h>
void db() { cerr << "\n"; }
template <class T, class... U>
void db(T a, U... b) { cerr << a << " ", db(b...); }
inline char gc()
{
const static int SZ = 1 << 16;
static char buf[SZ], *p1, *p2;
if (p1 == p2 && (p2 = buf + fread(p1 = buf, 1, SZ, stdin), p1 == p2))
return -1;
return *p1++;
}
void rd() {}
template <typename T, typename... U>
void rd(T &x, U &...y)
{
x = 0;
bool f = 0;
char c = gc();
while (!isdigit(c))
f ^= !(c ^ 45), c = gc();
while (isdigit(c))
x = (x << 1) + (x << 3) + (c ^ 48), c = gc();
f && (x = -x), rd(y...);
}
template <typename T>
void prt(T x)
{
if (x < 0)
putchar('-'), x = -x;
if (x > 9)
prt(x / 10);
putchar((x % 10) ^ 48);
}
const int N = 1005;
int dp[N][N], ar[N][N];
signed main()
{
int n;
rd(n);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= i; j++)
rd(ar[i][j]);
for (int i = n; i > 0; i--)
for (int j = 1; j <= i; j++)
dp[i][j] = max(dp[i + 1][j], dp[i + 1][j + 1]) + ar[i][j];
prt(dp[1][1]), putchar('\n');
}
```
----
## [CSES -- Dice Combinations](https://cses.fi/problemset/task/1633)
給定一個整數 $1\leq n\leq 10^6$ ，可以骰六面骰子任意次數，求有多少種方法使得點數總和是 $n$ ，順序交換算不同次
----
- 設$dp[i]$為總和$i$點的方法數
- $dp[i]=\sum_{k=1}^{6}{dp[i-k]}$
- $dp[0]=1$
- $i-k\geq 0$
----
程式碼：
```cpp!
#include <bits/stdc++.h>
using namespace std;
const int M=1e9+7;
signed main(){
int n;
scanf("%d",&n);
vector<int> dp(n+1,0);
dp[0]=1;
for (int i=1;i<=n;i++){
for (int j=1;j<=6&&j<=i;j++){
(dp[i]+=dp[i-j])%=M;
}
}
printf("%d\n",dp[n]);
}
```
----
## [CSES --Maximum Subarray Sum](https://cses.fi/problemset/task/1643)
給出一個數列$a$，$-10^9\leq a_i\leq 10^9$，求數列的最長非空連續和
----
- 設dp[i]為考慮i以前，選了i的最長連續和
- $dp[i]=max(a_i,a_i+dp[i-1])$
- $dp[0]=0$
- 答案是 $max \{dp[i]\ |\ i>0\}$
----
程式碼：
```cpp!
#include <bits/stdc++.h>
#define lowbit(x) ((x) & -(x))
#define ml(a, b) ((1ll * (a) * (b)) % M)
#define tml(a, b) (a) = ((1ll * (a) * (b)) % M)
#define ad(a, b) ((0ll + (a) + (b)) % M)
#define tad(a, b) (a) = ((0ll + (a) + (b)) % M)
#define mi(a, b) ((0ll + M + (a) - (b)) % M)
#define tmi(a, b) (a) = ((0ll + M + (a) - (b)) % M)
#define tmin(a, b) (a) = min((a), (b))
#define tmax(a, b) (a) = max((a), (b))
#define iter(a) (a).begin(), (a).end()
#define riter(a) (a).rbegin(), (a).rend()
#define init(a, b) memset((a), (b), sizeof(a))
#define cpy(a, b) memcpy((a), (b), sizeof(a))
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define pb emplace_back
#define mpr make_pair
#define ls(i) ((i) << 1)
#define rs(i) ((i) << 1 | 1)
#define INF 0x3f3f3f3f
#define NIF 0xc0c0c0c0
#define eps 1e-9
#define F first
#define S second
#define AC cin.tie(0)->sync_with_stdio(0)
using namespace std;
typedef long long llt;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<llt, llt> pll;
typedef complex<double> cd;
// const int M = 998244353;
// random_device rm;
// mt19937 rg(rm());
// default_random_engine rg(rm());
// uniform_int_distribution<int> rd(INT_MIN, INT_MAX);
// uniform_real_distribution<double> rd(0, M_PI);
void db() { cerr << "\n"; }
template <class T, class... U>
void db(T a, U... b) { cerr << a << " ", db(b...); }
template <typename T>
void rd(T &x)
{
x = 0;
bool f = 0;
char c = getchar();
while (!isdigit(c))
f ^= !(c ^ 45), c = getchar();
while (isdigit(c))
x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
f && (x = -x);
}
template <typename T>
void prt(T x)
{
if (x < 0)
putchar('-'), x = -x;
if (x > 9)
prt(x / 10);
putchar((x % 10) ^ 48);
}
signed main()
{
llt n, cr = 0, mx = 0, x, b = -INF;
rd(n);
while (n--)
{
rd(x);
tmax(b, x);
cr += x;
tmax(cr, 0ll);
tmax(mx, cr);
}
if (b < 0)
prt(b);
else
prt(mx);
}
```
----
## 推薦提單：
[CSES -- Dynamic Programming](https://cses.fi/problemset/)
基礎技巧，相對簡單
[Atcoder -- dp contest](https://atcoder.jp/contests/dp)
前面基礎技巧，後面有基礎優化
[Luogu -- DP](https://www.luogu.com.cn/training/1435)
涵蓋範圍超大，刷完就是dp神了
---
# 經典問題
----
## [UVA -- 10405](https://zerojudge.tw/ShowProblem?problemid=c001)
給出兩個字串$s,t$，求兩個字串的最長共同子序列長度，$1\leq|s|,|t|,\leq 2000$
子序列：透過刪除任意數量元素（含0或全部），剩下來的序列（按原順序）
----
- dp[i][j]為s長度為i前綴與t長度j前綴的LCS
- $s[i]=t[j]\Rightarrow dp[i][j]=dp[i-1][j-1]+1$
- $dp[i][j]=max(dp[i-1][j],dp[i][j-1])$
- $dp[i][0] = dp[0][j] = 0$
- 答案：$dp[|s|][|t|]$
----
## 滾動陣列
- 觀察到dp[i][?]僅會用到dp[i-1][?]
- 迭代到dp[i][?]時dp[i-1][?]以前沒用
- 可以用兩個陣列交替
- dp[i][j]只會用到$dp[k][l],k\leq i\ \&\ l\leq j$
- 僅用到比自己小，先更新大再更新小
- 只需要一條陣列
----
程式碼：
```cpp!
#include <bits/stdc++.h>
#define eps 1e-9
#define F first
#define S second
#define AC ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
typedef long long llt;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<llt, llt> pll;
string s1, s2;
int ln1, ln2;
int dp[2000];
int main()
{
AC;
while (getline(cin, s1) && getline(cin, s2))
{
ln1 = s1.length();
ln2 = s2.length();
memset(dp, 0, sizeof(dp));
for (int i = 0; i < ln1; i++)
{
for (int j = ln2; j > 0; j--)
if (s1[i] == s2[j - 1])
dp[j] = dp[j - 1] + 1;
for (int j = 1; j <= ln2; j++)
dp[j] = max(dp[j - 1], dp[j]);
}
printf("%d\n", dp[ln2]);
}
}
```
----
## [Atecoder -- LCS](https://atcoder.jp/contests/dp/tasks/dp_f)
給出兩個字串$s,t$，求一組兩個字串的最長共同子序列，$1\leq|s|,|t|,\leq 2000$
----
- 需要進行回朔
- 紀錄轉移點來源fr[i][j]
- 就會形成一張圖，邊指向的轉移點
- 使用滾動陣列就很麻煩了
- [卡記憶體得回朔題](https://codeforces.com/problemset/problem/101/E)
----
程式碼：
```cpp!
#include <bits/stdc++.h>
#define lowbit(x) ((x) & -(x))
#define eps 1e-9
#define F first
#define S second
#define AC ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
typedef long long llt;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<llt, llt> pll;
signed main()
{
AC;
int ln1, ln2;
string s1, s2;
cin >> s1 >> s2;
ln1 = s1.length(), ln2 = s2.length();
vector<int> dp(ln1 + 1, 0);
vector<string> ds(ln1 + 1, "");
for (int i = 0; i < ln2; i++)
{
for (int j = ln1; j > 0; j--)
{
if (s1[j - 1] == s2[i])
{
dp[j] = dp[j - 1] + 1;
ds[j] = ds[j - 1];
ds[j].push_back(s2[i]);
}
}
for (int j = 1; j <= ln1; j++)
{
if (dp[j] < dp[j - 1])
{
dp[j] = dp[j - 1];
ds[j] = ds[j - 1];
}
}
}
cout << ds[ln1] << '\n';
}
```
----
## [CSES --Increasing Subsequence](https://cses.fi/problemset/task/1145)
給出一個序列，求最長嚴格遞增子序列長度
----
- 定義dp[i]為考慮i以前，選$a_i$的答案
- $dp[i]=max(1,max\{dp[j]\ |\ j<i\ \land\ a_j<a_i\})$
- $dp[0]=0,ans=max\{dp[i]\}$
- $O(n^2)$不會過，需要優化
----
解法一：二分搜壓轉移
- dp[i]定義長度為i的最小結尾
- 每加入一個數$a_i$，二分搜$max\{j\ |\ dp[j]<a_i\}$
- 更新$dp[j]=a_i$
- dp[0]=-INF
- 加入$a_i$需要O(logn)，總共O(nlogn)會過
----
程式碼：
```cpp!
#include <bits/dtfc++.h>
#define lowbit(x) ((x) & -(x))
#define INF 0x3f3f3f3f
#define eps 1e-9
#define F first
#define S second
#define AC ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
typedef long long llt;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<llt, llt> pll;
int ar[200005];
signed main()
{
int n, x;
memset(ar, INF, sizeof(ar));
scanf("%d", &n);
while (n-- && scanf("%d", &x))
*lower_bound(ar, ar + 200005, x) = x;
for (x = 0; ar[x] != INF; x++)
;
printf("%d\n", x);
}
```
----
解法二：資料結構優化
- 定義dp[i]為考慮i以前，選$a_i$的答案
- 線段樹或bit存a_i小於一定值的最大dp值
- 轉移時取dp[i]=線段樹$a_i$前綴+1
- 更新線段樹以dp[i]更新線段樹$a_i$位置
- 值域太大須離散化
---
# 背包問題
----
## [Atcoder -- D - Knapsack 1](https://atcoder.jp/contests/dp/tasks/dp_d)
有$N$種物品，每個物品有重量$w_i$與價值$v_i$，對於每個物品可以選或是不選，求選的物品重量不超過$W$的情況，價值總和最大是多少？
$1\leq N \leq 100,1\leq w_i\leq W\leq 10^5,1\leq v_i\leq10^9$
- 又被稱為01背包問題，代表選或是不選
----
- 定義dp[i][j]為前 i 個物品總重量$\leq j$ 的最大價值
- $dp[i][j] = max(dp[i-1][j],dp[i-1][j-w_i]+v_i)$
- $dp[0][j]=0$
- 總複雜度O(NW)，可以壓成一條陣列
----
程式碼：
```cpp!
#include <bits/stdc++.h>
#define lowbit(x) ((x) & -(x))
#define eps 1e-9
#define F first
#define S second
#define AC ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
typedef long long llt;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<llt, llt> pll;
signed main()
{
int n, lmt, w, v;
scanf("%d%d", &n, &lmt);
vector<llt> dp(lmt + 1, 0);
while (n-- && scanf("%d%d", &w, &v))
{
for (int i = lmt; i >= w; i--)
dp[i] = max(dp[i], dp[i - w] + v);
}
printf("%lld\n", dp[lmt]);
}
```
----
## [Atcoder -- D - Knapsack 2](https://atcoder.jp/contests/dp/tasks/dp_e)
有$N$種物品，每個物品有重量$w_i$與價值$v_i$，對於每個物品可以選或是不選，求選的物品重量不超過$W$的情況，價值總和最大是多少？
$1\leq N \leq 100,1\leq w_i\leq W\leq 10^9,1\leq v_i\leq 10^3$
- 重量很大，價值很小
----
- 定義dp[i][j]為前 i 個物品總價值$\geq j$ 的最小重量
- $dp[i][j] = min(dp[i-1][j],dp[i-1][j-v_i]+w_i)$
- $dp[0][0]=0,dp[0][j>0]=INF$
- 總複雜度$O(N\sum{v_i})$，可以壓成一條陣列
- 答案取$max\{i\ |\ dp[N][i]\leq W\}$
----
程式碼：
```cpp!
#include <bits/stdc++.h>
#define lowbit(x) ((x) & -(x))
#define eps 1e-9
#define N 100005
#define F first
#define S second
#define AC ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
typedef long long llt;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<llt, llt> pll;
signed main()
{
int n, lmt, w, v;
scanf("%d%d", &n, &lmt);
vector<int> dp(N, lmt + 1);
dp[0] = 0;
while (n-- && scanf("%d%d", &w, &v))
{
for (int i = N - 1; i >= v; i--)
dp[i] = min(dp[i], dp[i - v] + w);
}
v = N - 1;
while (dp[v] > lmt)
v--;
printf("%d\n", v);
}
```
----
## [luogu -- 疯狂的采药](https://www.luogu.com.cn/problem/P1616)
有$N$種物品，每個物品有重量$w_i$與價值$v_i$，對於每個物品可以選任意數量，求選的物品重量不超過$W$的情況，價值總和最大是多少？
$1\leq N \leq 100,1\leq w_i\leq W\leq 10^5,1\leq v_i\leq10^9$
- 無限背包問題，每種物品有無限個
----
- 定義dp[i][j]為前 i 個物品總重量$\leq j$ 的最大價值
- $dp[i][j] = max(dp[i-1][j],dp[i][j-w_i]+v_i)$
- $dp[0][j]=0$
- 總複雜度O(NW)，可以壓成一條陣列
- 因為重複轉移，所以迴圈順序要改
----
程式碼：
```cpp!
#include <bits/stdc++.h>
#define eps 1e-9
#define F first
#define S second
#define AC ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
typedef long long llt;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<llt, llt> pll;
int main()
{
int n, m, w, v;
cin >> n >> m;
vector<llt> dp(n + 1, 0);
while (m-- && cin >> w >> v)
{
for (int i = w; i <= n; i++)
dp[i] = max(dp[i], dp[i - w] + v);
}
cout << dp[n] << '\n';
}
```
----
## [luogu -- 宝物筛选](https://www.luogu.com.cn/problem/P1776)
有$N$種物品，每個物品有重量$w_i$價值$v_i$與數量$c_i$，對於第i個物品可以選任意$\leq c_i$ 數量，求選的物品重量不超過$W$的情況，價值總和最大是多少？
$1\leq N \leq 100,1\leq w_i\leq W\leq 10^4,1\leq v_i\leq10^9,c_i\leq 10^5$
- 有限背包問題，每種物品有數量限制，不一定是1
----
解法一：二的冪次
- 物品一定數量打包一起，看成一個
- t個物品打包，$w'=w_i\times t,v'=v_i\times t$
- 將物品數量拆成二的冪次
- $c_i=2^{\log_{2}c_i}-1+k$
- 後面一個物品，前面$\log_{2}c_i$個物品
- 拆好物品用01背包問題解
- 複雜度 $O(W\sum\log_2 c_i )$
----
程式碼：
```cpp!
#include <bits/stdc++.h>
using namespace std;
typedef long long llt;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<llt, llt> pll;
signed main()
{
int n, m, c;
llt v, w;
scanf("%d%d", &n, &m);
vector<llt> dp(m + 1, 0);
while (n-- && scanf("%lld%lld%d", &v, &w, &c))
{
for (llt cr = 1; cr <= c; cr <<= 1)
{
c -= cr;
llt cv = v * cr, cw = w * cr;
for (int i = m; i >= cw; i--)
dp[i] = max(dp[i], dp[i - cw] + cv);
}
if (c)
{
llt cv = v * c, cw = w * c;
for (int i = m; i >= cw; i--)
dp[i] = max(dp[i], dp[i - cw] + cv);
}
}
printf("%lld\n", dp[m]);
}
```
----
解法二：單調隊列優化
----
程式碼：
```cpp!
#include <bits/stdc++.h>
#define pb emplace_back
#define mpr make_pair
#define ls(i) ((i) << 1)
#define rs(i) ((i) << 1 | 1)
#define INF 0x3f3f3f3f
#define NIF 0xc0c0c0c0
#define eps 1e-9
#define F first
#define S second
#define AC cin.tie(0)->sync_with_stdio(0)
using namespace std;
typedef long long llt;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<llt, llt> pll;
typedef complex<double> cd;
signed main()
{
int n, m, c;
llt v, w;
scanf("%d%d", &n, &m);
vector<llt> dp(m + 1, 0), tp(m + 1, 0);
while (n-- && scanf("%lld%lld%d", &v, &w, &c))
{
deque<llt> q[w];
for (int i = 0; i <= m; i++)
{
const int cr = i % w;
if (!q[cr].empty() && (i - q[cr].front()) / w > c)
q[cr].pop_front(); //數量超過pop
while (!q[cr].empty() &&
dp[i] >= dp[q[cr].back()] + (i - q[cr].back()) / w * v)
q[cr].pop_back(); //當前更優
q[cr].push_back(i);
tp[i] = dp[q[cr].front()] + (i - q[cr].front()) / w * v;
}
tp.swap(dp);
}
printf("%lld\n", dp[m]);
}
```
----
[CSES -- Coin Combinations II](https://cses.fi/problemset/task/1636)
有$n$種硬幣，幣值為$w_i$，求有多少種方法湊出$W$塊錢，不同順序算一同種
$1\leq n\leq 100,1\leq w_i\leq W\leq10^5$
- 類似背包問題，幣值看成重量，求達成特定重量方式
----
- 定義dp[i][j]為使用前i種硬幣湊j的方法數
- $dp[i][j]=dp[i-1][j]+dp[i][j-w_i]$
- dp[0][0]=1
- 類似無限背包，max改成加法
----
程式碼：
```cpp!
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
const int M=1e9+7;
signed main(){
int n,x,m;
scanf("%d%d",&m,&n);
vector<int> dp(n+1,0);
dp[0]=1;
while (m--&&scanf("%d",&x)){
for (int i=x;i<=n;i++)
(dp[i]+=dp[i-x])%=M;
}
printf("%d\n",dp[n]);
}
```
----
[CSES -- Coin Combinations I](https://cses.fi/problemset/task/1635)
有$n$種硬幣，幣值為$w_i$，求有多少種方法湊出$W$塊錢，不同順序算不同種
$1\leq n\leq 100,1\leq w_i\leq W\leq10^5$
- 怎沒算不同排列，排列組合有用？
----
- dp[i]定義湊出i塊的方法
- $dp[i]=\sum_{k\in w_i}{dp[i-k]}$
- dp[0]=1
- 錢變成轉移方式而不是物品
- 有時候轉移方式會根據輸入不同
----
程式碼：
```cpp!
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
const int M=1e9+7;
signed main(){
int n,x,m;
scanf("%d%d",&m,&n);
vector<int> dp(n+1,0),ar(m);
dp[0]=1;
for (int i=0;i<m;i++)
scanf("%d",&ar[i]);
for (int i=1;i<=n;i++){
for (int j:ar){
if (i>=j)
(dp[i]+=dp[i-j])%=M;
}
}
printf("%d\n",dp[n]);
}
```
---
# 區間dp
----
## [Atcoder -- Slimes](https://atcoder.jp/contests/dp/tasks/dp_n)
有一個長度為 $n$ 的序列，要選兩個相鄰的數$a_i,a_{i+1}$將其合併，花費是$a_i+a_{i+1}$，原本的位置留下$a_i+a_{i+1}$，請問最少要用多少花費才能將序列合併到長度為1?
$1\leq n\leq 400$
----
- dp[l][r]為合併區間[l,r]最小花費
- $dp[l][r]=\sum_{k=l}^{r}{a_k}+min\{dp[l][m]+dp[m+1][r]\ |\ m\in[l,r)\}$
- $dp[k][k]=0,ans=dp[1][n]$
- 轉移順序，長度小到長度大
----
程式碼：
```cpp!
#include <bits/stdc++.h>
#define lowbit(x) ((x) & -(x))
#define eps 1e-9
#define F first
#define S second
#define AC ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
typedef long long llt;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<llt, llt> pll;
signed main()
{
int n;
scanf("%d", &n);
vector<int> ar(n);
vector<vector<llt>> dp(n, vector<llt>(n, LLONG_MAX));
for (int i = 0; i < n; i++)
scanf("%d", &ar[i]), dp[i][i] = 0;
for (int k = 1; k < n; k++)
{
llt sum = 0;
for (int i = 0; i < k; i++)
sum += ar[i];
for (int i = k; i < n; i++)
{
sum += ar[i];
for (int j = i - k; j < i; j++)
dp[i - k][i] = min(dp[i - k][j] + dp[j + 1][i], dp[i - k][i]);
dp[i - k][i] += sum, sum -= ar[i - k];
}
}
printf("%lld\n", dp[0][n - 1]);
}
```
----
## [NOI2007 -- 矩阵取数游戏](https://www.luogu.com.cn/problem/P1005)
給定一個 $n$ 行 $m$ 列的矩陣，每次從每一行頭或尾取出一個數字，一次共 $n$ 個 $m$ 次取完，設第 $i$ 次取的元素和為 $s_i$ ，可獲得 $s_i\times 2^i$ 分，求最大得分
$1\leq n,m\leq 80$
----
- 每一行是獨立的，考慮一行做 $n$ 次
- 設 $dp[l][r]$ 為序列 $a_l...a_r$ 的答案
- $dp[l][r]=max(dp[l+1][r]+a_l\times 2^k,$
$dp[l][r-1]+a_r\times 2^k),k=m-r+l$
- $dp[i][i]=a_i\times 2^m$
- 記得要用int128或是自己寫大數運算
----
程式碼：
```cpp!
#include <bits/stdc++.h>
#define lowbit(x) ((x) & -(x))
#define ml(a, b) ((1ll * (a) * (b)) % M)
#define tml(a, b) (a) = ((1ll * (a) * (b)) % M)
#define ad(a, b) ((0ll + (a) + (b)) % M)
#define tad(a, b) (a) = ((0ll + (a) + (b)) % M)
#define mi(a, b) ((0ll + M + (a) - (b)) % M)
#define tmi(a, b) (a) = ((0ll + M + (a) - (b)) % M)
#define tmin(a, b) (a) = min((a), (b))
#define tmax(a, b) (a) = max((a), (b))
#define iter(a) (a).begin(), (a).end()
#define riter(a) (a).rbegin(), (a).rend()
#define init(a, b) memset((a), (b), sizeof(a))
#define cpy(a, b) memcpy((a), (b), sizeof(a))
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define pb emplace_back
#define mpr make_pair
#define ls(i) ((i) << 1)
#define rs(i) ((i) << 1 | 1)
#define INF 0x3f3f3f3f
#define NIF 0xc0c0c0c0
#define eps 1e-9
#define F first
#define S second
#define AC cin.tie(0)->sync_with_stdio(0)
using namespace std;
typedef long long llt;
typedef __int128_t lll;
typedef pair<int, int> pii;
void db() { cerr << "\n"; }
template <class T, class... U>
void db(T a, U... b) { cerr << a << " ", db(b...); }
template <typename T>
void rd(T &x)
{
x = 0;
bool f = 0;
char c = getchar();
while (!isdigit(c))
f ^= !(c ^ 45), c = getchar();
while (isdigit(c))
x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
f && (x = -x);
}
template <typename T>
void prt(T x)
{
if (x < 0)
putchar('-'), x = -x;
if (x > 9)
prt(x / 10);
putchar((x % 10) ^ 48);
}
const int N = 90;
lll dp[N][N], pl[N];
int ar[N];
signed main()
{
pl[0] = 1;
for (int i = 1; i < N; i++)
pl[i] = pl[i - 1] << 1;
int n, m;
rd(n), rd(m);
lll ans = 0;
while (n--)
{
for (int i = 0; i < m; i++)
rd(ar[i]), dp[i][i] = pl[m] * ar[i];
for (int l = 1; l < m; l++)
for (int r = l; r < m; r++)
dp[r - l][r] = max(dp[r - l + 1][r] + ar[r - l] * pl[m - l],
dp[r - l][r - 1] + ar[r] * pl[m - l]);
ans += dp[0][m - 1];
}
prt(ans), putchar('\n');
}
```
----
## 環狀dp
陣列是環狀，頭尾相接，所以會有一些變化
1. 分case
- 通常是區間dp會這樣處理
- 分成環狀不影響和有跨越頭尾的
- 尾端接開頭可以看成切區間
2. 陣列多複製一份
- 更常會這樣處理，尾端接第二份開始
- 可以正常dp，但要小心不要自己轉移自己
- 可以控制轉移距離<陣列長度
----
## [leetcode -- Maximum Sum Circular Subarray](https://leetcode.com/problems/maximum-sum-circular-subarray/)
給定一個序列，求環狀最大連續和
----
- 採用方法一，分成一般區間和跨越頭尾
- 一般區間用原本的greedy或dp解
- 特殊區間用總和扣區間連續最小和
- 兩個結果取max就是答案
----
程式碼：
```cpp!
class Solution {
public:
int maxSubarraySumCircular(vector<int>& ar) {
int sum = 0, mn = INT_MAX, mx = INT_MIN, sx = 0, sn = 0;
for (auto i : ar) {
sn=min(sn+i,i);
sx=max(sx+i,i);
mx=max(mx,sx);
mn=min(mn,sn);
sum+=i;
}
return sum-mn==0?mx:max(sum-mn,mx);
}
};
```
----
## [NOI1995 -- 石子合并](https://www.luogu.com.cn/problem/P1880)
有 $n$ 堆石頭排成圓形，第 $i$ 堆石頭有 $a_i$ 顆，每次要將兩堆石頭合併，得分是合併後該堆石頭數量，求合併成一堆的最大和最小得分
----
- 採用方法二複製一份陣列，dp式與之前一樣
- 答案取$max\{dp[l][l+n-1]\ |\ l\in[1,n]\}$
- 有一個間隔不會被合併，可以斷環為鍊
- 可以把狀態改成左界位置與長度
----
程式碼：
```cpp!
#include <bits/stdc++.h>
using namespace std;
typedef long long llt;
void db() { cerr << "\n"; }
template <class T, class... U>
void db(T a, U... b) { cerr << a << " ", db(b...); }
inline char gc()
{
const static int SZ = 1 << 16;
static char buf[SZ], *p1, *p2;
if (p1 == p2 && (p2 = buf + fread(p1 = buf, 1, SZ, stdin), p1 == p2))
return -1;
return *p1++;
}
void rd() {}
template <typename T, typename... U>
void rd(T &x, U &...y)
{
x = 0;
bool f = 0;
char c = gc();
while (!isdigit(c))
f ^= !(c ^ 45), c = gc();
while (isdigit(c))
x = (x << 1) + (x << 3) + (c ^ 48), c = gc();
f && (x = -x), rd(y...);
}
template <typename T>
void prt(T x)
{
if (x < 0)
putchar('-'), x = -x;
if (x > 9)
prt(x / 10);
putchar((x % 10) ^ 48);
}
const int N = 205;
int ar[N], mx[N][N], mn[N][N];
signed main()
{
int n;
rd(n);
for (int i = 0; i < n; i++)
rd(ar[i]), ar[i + n] = ar[i];
int n2 = n << 1;
for (int r = 0; r < n2; r++)
{
int sum = ar[r];
for (int t = 1; t < n; t++)
{
int l = r - t;
if (l < 0)
break;
mx[l][r] = ~INF, mn[l][r] = INF;
sum += ar[l];
for (int k = l; k < r; k++)
tmax(mx[l][r], mx[l][k] + mx[k + 1][r]),
tmin(mn[l][r], mn[l][k] + mn[k + 1][r]);
mx[l][r] += sum, mn[l][r] += sum;
}
}
int anx = ~INF, ann = INF;
for (int i = 0; i < n; i++)
tmax(anx, mx[i][i + n - 1]), tmin(ann, mn[i][i + n - 1]);
prt(ann), putchar('\n');
prt(anx), putchar('\n');
}
```
---
# 樹型dp
----
## 暖身題
有一棵 $n$ 個節點的樹，每個點上有點權 $v_i$ ，接下來有 $q$ 筆詢問，每筆詢問有兩種類型
- 將節點 i 的權重改為 k
- 詢問與節點 i 相鄰節點的點權和
$1\leq n,q\leq 10^5$
----
- 每次修改更新鄰居？
- 每次詢問加總鄰居？
- 一個點可以連O(n)條邊
- 總複雜度 O(nq) $\Rightarrow$ TLE
----
- 每次修改時更新父節點
- 每次詢問時小孩都已經算好的
- 再加上父節點的權值就是答案
- 複雜度 O(n+q)
#### 結論：善用父節點只有一個，均攤掉複雜度
----
## [树的深度及子树大小](https://vjudge.net/problem/51Nod-2627)
給出一棵 $n$ 個節點的樹，節點1是根節點，求每個的深度和子樹大小
$1\leq n\leq 10^5$
----
- 深度為父節點深度+1
- 子樹大小 $sz[u]=1+\sum_{(u,v)\in E}{sz[v]}$
- 在dfs子節點時，先更新子節點深度
- 拜訪完子節點更新父節點大小
----
## [Luogu -- 沒有上司的舞會](https://www.luogu.com.cn/problem/P1352)
給出一棵 $n$ 個節點的有根樹，節點有點權 $v_i$ ，我們想選一些節點，但是若選了節點 $u$ ，其父節點就不能選，求能選出的最大點權和
$1\leq n\leq 10^5$
----
- 定義 dp[0][u]為不選 u 其子樹點權最大和
- 定義 dp[1][u]為選 u 後其子樹點權最大和
- $dp[1][u] = v_i+\sum_{(u,v)\in E}{dp[0][v]}$
- $dp[0][u] = \sum_{(u,v)\in E}{max(dp[0][v],dp[1][v])}$
----
程式碼：
```cpp!
#include <bits/stdc++.h>
#define lowbit(x) ((x) & -(x))
#define ml(a, b) ((1ll * (a) * (b)) % M)
#define tml(a, b) (a) = ((1ll * (a) * (b)) % M)
#define ad(a, b) ((0ll + (a) + (b)) % M)
#define tad(a, b) (a) = ((0ll + (a) + (b)) % M)
#define mi(a, b) ((0ll + M + (a) - (b)) % M)
#define tmi(a, b) (a) = ((0ll + M + (a) - (b)) % M)
#define tmin(a, b) (a) = min((a), (b))
#define tmax(a, b) (a) = max((a), (b))
#define iter(a) (a).begin(), (a).end()
#define riter(a) (a).rbegin(), (a).rend()
#define init(a, b) memset((a), (b), sizeof(a))
#define cpy(a, b) memcpy((a), (b), sizeof(a))
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define pb emplace_back
#define mpr make_pair
#define ls(i) ((i) << 1)
#define rs(i) ((i) << 1 | 1)
#define INF 0x3f3f3f3f
#define NIF 0xc0c0c0c0
#define eps 1e-9
#define F first
#define S second
#define AC cin.tie(0)->sync_with_stdio(0)
using namespace std;
typedef long long llt;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<llt, llt> pll;
typedef complex<double> cd;
const int N = 6005;
vector<int> eg[N];
int d1[N], d2[N], ar[N];
bool vd[N];
void dfs(int u)
{
d1[u] = ar[u], d2[u] = 0;
for (const int &v : eg[u])
{
dfs(v);
d1[u] += d2[v];
d2[u] += max(d2[v], d1[v]);
}
}
signed main()
{
int n, x, y, ans;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &ar[i]);
for (int i = 1; i < n; i++)
{
scanf("%d%d", &x, &y);
eg[y].pb(x), vd[x] = 1;
}
for (int i = 1; i <= n; i++)
{
if (vd[i])
continue;
dfs(i), ans = max(d1[i], d2[i]);
}
printf("%d\n", ans);
}
```
----
## [Luogu -- 选课](https://www.luogu.com.cn/problem/P2014)
給出一棵 $n$ 個節點樹，根節點是0，每個節點有點權 $v_i$ ，我們想選 $m$ 個節點，使得點權和最大，但是若選的一個節點，其父節點也必須選，也就是所有祖先都要選，求最大的點權和是多少？
- 樹背包問題，北市賽有出過
----
- 定義dp[i][j]為節點i子樹選了j個點的最大和
- 子樹要選代表節點i也要選
- dp[i][j]會依序被子節點更新
- 被更新後代表選了一部分子樹，定義稍稍改變
- $dp[i][j]=max(dp[i][j],dp[v][k]+dp[i][j-k]),(i,v)\in E\land j>k$
- 有 $n^2$個子節點要更新，每次更新 $n$，複雜度 $O(n^3)$
- 觀察到子樹大小有限，會轉移很多沒用的點
- 再dp子樹大小，只轉移有用的點，可以證明複雜度是 $O(n^2)$
----
程式碼：
```cpp!
#include <bits/stdc++.h>
#define lowbit(x) ((x) & -(x))
#define ml(a, b) ((1ll * (a) * (b)) % M)
#define tml(a, b) (a) = ((1ll * (a) * (b)) % M)
#define ad(a, b) ((0ll + (a) + (b)) % M)
#define tad(a, b) (a) = ((0ll + (a) + (b)) % M)
#define mi(a, b) ((0ll + M + (a) - (b)) % M)
#define tmi(a, b) (a) = ((0ll + M + (a) - (b)) % M)
#define tmin(a, b) (a) = min((a), (b))
#define tmax(a, b) (a) = max((a), (b))
#define iter(a) (a).begin(), (a).end()
#define riter(a) (a).rbegin(), (a).rend()
#define init(a, b) memset((a), (b), sizeof(a))
#define cpy(a, b) memcpy((a), (b), sizeof(a))
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define pb emplace_back
#define mpr make_pair
#define ls(i) ((i) << 1)
#define rs(i) ((i) << 1 | 1)
#define INF 0x3f3f3f3f
#define NIF 0xc0c0c0c0
#define eps 1e-9
#define F first
#define S second
#define AC cin.tie(0)->sync_with_stdio(0)
using namespace std;
typedef long long llt;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<llt, llt> pll;
typedef complex<double> cd;
const int N = 305;
vector<int> eg[N];
int dp[N][N], fa[N], ar[N], sz[N];
void dfs(int u)
{
dp[u][1] = ar[u], sz[u] = 1;
for (const int &v : eg[u])
{
dfs(v), sz[u] += sz[v];
for (int i = sz[u]; i > 0; i--)
for (int j = min(sz[v], i - 1); j > 0; j--)
tmax(dp[u][i], dp[u][i - j] + dp[v][j]);
}
}
signed main()
{
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
{
scanf("%d%d", &fa[i], &ar[i]);
eg[fa[i]].pb(i);
}
dfs(0);
printf("%d\n", dp[0][m + 1]);
}
```
----
## 換根dp
- 我們發現根節點固定以後性質很好
- dp根節點很容易，但是根不固定
- 將根題換成相鄰的點，dp值只有更換的兩點變化
- 根據dfs序更換根節點，算出需要的答案
----
## [Luogu -- STA-Station](https://www.luogu.com.cn/problem/P3478)
給定一棵 $n$ 個節點的樹，求以哪個節點為根，所有節點的深度總和最大，若有多個答案，輸出任意一個即可
- 裸題，直接告訴你要選不同根
----
- 固定一個根，dp可以很好 O(n) 算出深度總和
- 定一個根，定義dp[u]為 u 節點子樹的深度和
- $dp[u] = \sum_{(u,v)\in E}{dp[v]+sz[v]}$
- 我們可以 O(1) 將根節點從 u 換成小孩 v
- $dp[u]=dp[u]-dp[v]-sz[v],sz[u]=sz[u]-sz[v]$
- $dp[v]=dp[v]+dp[u]+sz[u],sz[v]=sz[v]+sz[u]$
- 記得走完一個子節點要還原
----
程式碼：
```cpp!
#include <bits/stdc++.h>
#define lowbit(x) ((x) & -(x))
#define ml(a, b) ((1ll * (a) * (b)) % M)
#define tml(a, b) (a) = ((1ll * (a) * (b)) % M)
#define ad(a, b) ((0ll + (a) + (b)) % M)
#define tad(a, b) (a) = ((0ll + (a) + (b)) % M)
#define mi(a, b) ((0ll + M + (a) - (b)) % M)
#define tmi(a, b) (a) = ((0ll + M + (a) - (b)) % M)
#define tmin(a, b) (a) = min((a), (b))
#define tmax(a, b) (a) = max((a), (b))
#define iter(a) (a).begin(), (a).end()
#define riter(a) (a).rbegin(), (a).rend()
#define init(a, b) memset((a), (b), sizeof(a))
#define cpy(a, b) memcpy((a), (b), sizeof(a))
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define pb emplace_back
#define mpr make_pair
#define ls(i) ((i) << 1)
#define rs(i) ((i) << 1 | 1)
#define INF 0x3f3f3f3f
#define NIF 0xc0c0c0c0
#define eps 1e-9
#define F first
#define S second
#define AC cin.tie(0)->sync_with_stdio(0)
using namespace std;
typedef long long llt;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<llt, llt> pll;
typedef complex<double> cd;
const int N = 1e6 + 5;
vector<int> eg[N];
llt dp[N], sz[N], ans;
int p;
void dfs(int u, int fa)
{
dp[u] = 0, sz[u] = 1;
for (const int &v : eg[u])
{
if (v == fa)
continue;
dfs(v, u);
sz[u] += sz[v], dp[u] += dp[v] + sz[v];
}
}
void slv(int u, int fa)
{
if (dp[u] > ans)
ans = dp[u], p = u;
for (const int &v : eg[u])
{
if (v == fa)
continue;
dp[u] -= dp[v] + sz[v], sz[u] -= sz[v];
dp[v] += dp[u] + sz[u], sz[v] += sz[u];
slv(v, u);
dp[v] -= dp[u] + sz[u], sz[v] -= sz[u];
dp[u] += dp[v] + sz[v], sz[u] += sz[v];
}
}
signed main()
{
int n, x, y;
scanf("%d", &n);
for (int i = 1; i < n; i++)
{
scanf("%d%d", &x, &y);
eg[x].pb(y);
eg[y].pb(x);
}
dfs(1, -1), slv(1, -1);
printf("%d\n", p);
}
```
---
# 前綴優化
- 單純計算前後綴和或極值
- 快速計算區間和，可以乘倍數($ps[i]=\sum_{k=1}^i{a_k\times k}$)
- 配合差分運用，令$a_i=\sum_{k=1}^i{f_k}$
----
## [TIOJ -- 最大不連續和問題](https://tioj.ck.tp.edu.tw/problems/2048)
給定一個序列，求其最大不連續和，不連續指不完全連續，不一定要完全分開
- 基礎運用
----
- 計算前綴後綴最大和（可不連續）
- 枚舉空格，一個空格答案是前綴＋後綴
- 所有答案取max
----
程式碼：
```cpp!
#include <bits/stdc++.h>
#define lowbit(x) ((x) & -(x))
#define eps 1e-9
#define F first
#define S second
#define AC ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
typedef long long llt;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<llt, llt> pll;
signed main()
{
int n;
llt ans = LLONG_MIN;
scanf("%d", &n);
vector<llt> vr(n, 0);
for (int i = 0; i < n; i++)
scanf("%lld", &vr[i]);
vector<llt> fr(vr.begin(), vr.end());
vector<llt> br(vr.begin(), vr.end());
for (int i = 1; i < n; i++)
fr[i] = max(fr[i], fr[i - 1] + max(0ll, fr[i]));
for (int i = n - 2; i >= 0; i--)
br[i] = max(br[i], br[i + 1] + max(0ll, br[i]));
for (int i = 1; i < n - 1; i++)
ans = max(ans, fr[i - 1] + br[i + 1]);
printf("%lld\n", ans);
}
```
----
## [BJOI2018 -- 求和](https://www.luogu.com.cn/problem/P4427)
給定一棵跟節點為 $1$ 的樹，接下來有 $q$ 比詢問，每次求 $u$ 到 $v$ 路徑上節點深度的 $k$ 次方和，深度定義是到跟節點路徑上的邊數
$1\leq n,q\leq3\times10^5$
$1\leq k\leq50$
----
- 用樹上前綴和來解
- dp[i][x] 為根節點到 $x$ 深度的 $k$ 次方和
- 將路徑拆分成到根節點的路徑
- $ans=dp[k][u]+dp[k][v]-$
$(dp[k][lca(u,v)]\times 2+dep(lca(u,v))^k)$
- 差分的問題同理
----
程式碼：
```cpp!
// #pragma GCC optimize("Ofast,no-stack-protector")
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx,avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#define lowbit(x) ((x) & -(x))
#define ml(a, b) ((1ll * (a) * (b)) % M)
#define tml(a, b) (a) = ((1ll * (a) * (b)) % M)
#define ad(a, b) ((0ll + (a) + (b)) % M)
#define tad(a, b) (a) = ((0ll + (a) + (b)) % M)
#define mi(a, b) ((0ll + M + (a) - (b)) % M)
#define tmi(a, b) (a) = ((0ll + M + (a) - (b)) % M)
#define tmin(a, b) (a) = min((a), (b))
#define tmax(a, b) (a) = max((a), (b))
#define iter(a) (a).begin(), (a).end()
#define riter(a) (a).rbegin(), (a).rend()
#define inin(a, b) memset((a), (b), sizeof(a))
#define cpy(a, b) memcpy((a), (b), sizeof(a))
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define size(x) (int)x.size()
#define pb emplace_back
#define mpr make_pair
#define ls(i) ((i) << 1)
#define rs(i) ((i) << 1 | 1)
#define INF 0x3f3f3f3f
#define NIF 0xc0c0c0c0
#define eps 1e-9
#define F first
#define S second
#define AC cin.tie(0)->sync_with_stdio(0)
using namespace std;
typedef long long llt;
typedef unsigned long long ull;
typedef __int128_t lll;
typedef pair<int, int> pii;
const int M = 998244353;
void db() { cerr << "\n"; }
template <class T, class... U>
void db(T a, U... b) { cerr << a << " ", db(b...); }
inline char gc()
{
const static int SZ = 1 << 16;
static char buf[SZ], *p1, *p2;
if (p1 == p2 && (p2 = buf + fread(p1 = buf, 1, SZ, stdin), p1 == p2))
return -1;
return *p1++;
}
void rd() {}
template <typename T, typename... U>
void rd(T &x, U &...y)
{
x = 0;
bool f = 0;
char c = gc();
while (!isdigit(c))
f ^= !(c ^ 45), c = gc();
while (isdigit(c))
x = (x << 1) + (x << 3) + (c ^ 48), c = gc();
f && (x = -x), rd(y...);
}
template <typename T>
void prt(T x)
{
if (x < 0)
putchar('-'), x = -x;
if (x > 9)
prt(x / 10);
putchar((x % 10) ^ 48);
}
const int N = 3e5 + 5;
int dp[50][N], in[N], ou[N], ct, ac[20][N];
vector<int> eg[N];
void dfs(int u, int fa, int d)
{
in[u] = ++ct;
for (int v : eg[u])
{
if (v == fa)
continue;
dp[0][v] = d;
for (int i = 1; i < 50; i++)
dp[i][v] = ml(dp[i - 1][v], d);
for (int i = 0; i < 50; i++)
tad(dp[i][v], dp[i][u]);
ac[0][v] = u;
for (int i = 1; i < 20; i++)
ac[i][v] = ac[i - 1][ac[i - 1][v]];
dfs(v, u, d + 1);
}
ou[u] = ct;
}
inline bool isa(int a, int p)
{
return in[a] <= in[p] && ou[p] <= ou[a];
}
inline int lca(int u, int v)
{
if (isa(u, v))
return u;
for (int i = 19; i >= 0; i--)
if (ac[i][u] && !isa(ac[i][u], v))
u = ac[i][u];
return ac[0][u];
}
signed main()
{
int n, q, x, y, k;
rd(n);
for (int i = 1; i < n; i++)
{
rd(x, y);
eg[x].pb(y);
eg[y].pb(x);
}
dfs(1, -1, 1);
rd(q);
while (q--)
{
rd(x, y, k);
int p = lca(x, y);
prt(mi(ad(dp[k - 1][x], dp[k - 1][y]),
ad(dp[k - 1][p], dp[k - 1][ac[0][p]])));
putchar('\n');
}
}
```
---
# 位元dp
- 也可以叫狀壓dp，用來壓縮狀態
- 把狀態用01表示（有或無）
- 數字二進位即可以代表狀態
- 狀態轉換成數字，就可以用陣列存資訊了
----
假設當前狀態為t，可以進行以下操作
- 判斷第k位是不是1 $\Rightarrow((t>>k)\&1)$
- 與狀態s取聯集 $\Rightarrow(s\ |\ t)$
- 與狀態s取聯集 $\Rightarrow(s\ \&\ t)$
- 與狀態s取差對稱集 $\Rightarrow(s\ \oplus\ t)$
----
## [ZJ -- 旅行銷售員問題](https://zerojudge.tw/ShowProblem?problemid=c239)
給定一個 $n\leq16$ 點的圖（以鄰接矩陣），求從任意一點開始，經過所有其他點後，回到原本的點，最長路徑除以最短路徑是多少？
- 最大最小本質一樣，差在取max取min，做兩次就可以
----
- 狀態定義，二進位是1，代表該點走過
- 設dp[i][s]為當前 i 點走過 s 最短路徑
- $dp[i][s] = min\{dp[j][s\oplus 2^j]+ar[j][i]\ |\ j\&s\}$
- $dp[j][s\ |\ 2^j] = max(dp[j][s\ |\ 2^j],\ dp[i][s]+ar[i][j])$
- 從誰開始都一樣，用1，答案是$dp[1][2^n-1]$
----
程式碼：
```cpp!
#include <bits/stdc++.h>
#define lowbit(x) ((x) & -(x))
#define ml(a, b) ((1ll * (a) * (b)) % M)
#define tml(a, b) (a) = ((1ll * (a) * (b)) % M)
#define ad(a, b) ((0ll + (a) + (b)) % M)
#define tad(a, b) (a) = ((0ll + (a) + (b)) % M)
#define mi(a, b) ((0ll + M + (a) - (b)) % M)
#define tmi(a, b) (a) = ((0ll + M + (a) - (b)) % M)
#define tmin(a, b) (a) = min((a), (b))
#define tmax(a, b) (a) = max((a), (b))
#define iter(a) (a).begin(), (a).end()
#define riter(a) (a).rbegin(), (a).rend()
#define inin(a, b) memset((a), (b), sizeof(a))
#define cpy(a, b) memcpy((a), (b), sizeof(a))
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define size(x) (int)x.size()
#define pb emplace_back
#define mpr make_pair
#define ls(i) ((i) << 1)
#define rs(i) ((i) << 1 | 1)
#define INF 0x3f3f3f3f
#define NIF 0xc0c0c0c0
#define eps 1e-9
#define F first
#define S second
#define AC cin.tie(0)->sync_with_stdio(0)
using namespace std;
typedef long long llt;
typedef unsigned long long ull;
typedef __int128_t lll;
typedef pair<int, int> pii;
const int N = 15;
int mx[N][1 << N], mn[N][1 << N], gd[N][N];
signed main()
{
int n;
while (~scanf("%d", &n))
{
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
scanf("%d", &gd[i][j]), gd[j][i] = gd[i][j];
inin(mn, INF), inin(mx, ~INF), mx[0][1] = mn[0][1] = 0;
for (int mk = 0; mk < 1 << n; mk++)
{
for (int i = 0; i < n; i++)
{
if (~(mk >> i) & 1)
continue;
for (int j = 0; j < n; j++)
if (~(mk >> j) & 1)
tmax(mx[j][mk ^ (1 << j)], mx[i][mk] + gd[i][j]),
tmin(mn[j][mk ^ (1 << j)], mn[i][mk] + gd[i][j]);
}
}
int anx = ~INF, ann = INF, msk = (1 << n) - 1;
for (int i = 0; i < n; i++)
tmax(anx, gd[0][i] + mx[i][msk]), tmin(ann, gd[0][i] + mn[i][msk]);
int g = __gcd(anx, ann);
anx /= g, ann /= g;
if (ann == 1)
printf("%d\n", anx);
else
printf("%d/%d\n", anx, ann);
}
}
```
----
## [UVA -- Mega Man's Mission](https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=2895)
有 $n \leq16$ 隻怪物，一開始玩家有特定武器，可以擊殺某些怪物，擊殺怪物會掉一個武器，可以擊殺令一些怪物，每個武器可以無限制重複使用，請問有多少種順序殺死所有怪物？
----
- 武器狀態第i是1代表可以擊殺怪物i
- 通關狀態第i位是1代表怪物i已死
- 對於一個通關狀態，武器狀態是固定
- 通關獲得武器與原始武器聯集
- 可用武器代表可以轉移出去的點
- dp[i]代表i狀態的方法數
- $dp[i\oplus 2^j]=dp[i\oplus 2^j]+dp[i],j\in i$ 狀態的武器
----
程式碼：
```cpp!
#include <cstdio>
#include <algorithm>
using namespace std;
int wp[65536], n;
long long s[65536] = {1};
bool vd[65536] = {1};
int gw()
{
int sum = 0;
long long x;
scanf("%lld", &x);
for (int i = 0; i < n; i++)
{
sum <<= 1;
sum += x & 1;
x /= 10;
}
return sum;
}
int main()
{
int t, x, lm;
scanf("%d", &t);
for (int ti = 1; ti <= t; ti++)
{
scanf("%d", &n);
lm = 1 << n;
fill(wp, wp + lm, gw());
fill(s + 1, s + lm, 0);
fill(vd + 1, vd + lm, 0);
for (int i = 0; i < n; i++)
{
x = gw();
for (int j = 1; j < lm; j++)
if ((j >> i) & 1)
wp[j] |= x;
}
for (int i = 0; i < lm; i++)
for (int j = 1; j + i < lm; j <<= 1)
if (!(i & j) && wp[i] & j)
s[i + j] += s[i];
printf("Case %d: %lld\n", ti, s[lm - 1]);
}
}
```
----
## [POI2004 -- PRZ](https://www.luogu.com.cn/problem/P5911)
有 $n$ 個人要過橋，每個人有重量 $w_i$ 與過橋時間 $t_i$ ，橋樑有限重 $W$ ，你可以將人分組，只要同組重量和不超過限重，過橋時間是組中最久的，求所有人都過橋最短需要多少時間
$1\leq n\leq16$
----
- 狀態定義：二進位的1代表已經過橋的人
- $dp[S]$ 為過橋人集合為 $S$ 的最短時間
- $dp[S]=min\{dp[S\oplus S']\ |\ S'\in S\ \&\ w(S)\leq W\}$
- 必須用子集枚舉，複雜度 $O(3^N)$
- $S$ 的子集已知 $S'$，下一個為$(S'-1)\&S$
- 模擬退火亂做（x
----
程式碼：
```cpp!
#include <bits/stdc++.h>
#define lowbit(x) ((x) & -(x))
#define ml(a, b) ((1ll * (a) * (b)) % M)
#define tml(a, b) (a) = ((1ll * (a) * (b)) % M)
#define ad(a, b) ((0ll + (a) + (b)) % M)
#define tad(a, b) (a) = ((0ll + (a) + (b)) % M)
#define mi(a, b) ((0ll + M + (a) - (b)) % M)
#define tmi(a, b) (a) = ((0ll + M + (a) - (b)) % M)
#define tmin(a, b) (a) = min((a), (b))
#define tmax(a, b) (a) = max((a), (b))
#define iter(a) (a).begin(), (a).end()
#define riter(a) (a).rbegin(), (a).rend()
#define inin(a, b) memset((a), (b), sizeof(a))
void db() { cerr << "\n"; }
template <class T, class... U>
void db(T a, U... b) { cerr << a << " ", db(b...); }
inline char gc()
{
const static int SZ = 1 << 16;
static char buf[SZ], *p1, *p2;
if (p1 == p2 && (p2 = buf + fread(p1 = buf, 1, SZ, stdin), p1 == p2))
return -1;
return *p1++;
}
void rd() {}
template <typename T, typename... U>
void rd(T &x, U &...y)
{
x = 0;
bool f = 0;
char c = gc();
while (!isdigit(c))
f ^= !(c ^ 45), c = gc();
while (isdigit(c))
x = (x << 1) + (x << 3) + (c ^ 48), c = gc();
f && (x = -x), rd(y...);
}
template <typename T>
void prt(T x)
{
if (x < 0)
putchar('-'), x = -x;
if (x > 9)
prt(x / 10);
putchar((x % 10) ^ 48);
}
const int N = 16;
int dp[1 << N], sum[1 << N], wr[N], tr[N];
signed main()
{
int W, n;
rd(W, n);
for (int i = 0; i < n; i++)
rd(tr[i], wr[i]);
for (int mk = 0; mk < 1 << n; mk++)
{
int tp = 0;
for (int i = 0; i < n; i++)
if ((mk >> i) & 1)
tmax(sum[mk], tr[i]), tp += wr[i];
if (tp > W)
sum[mk] = INF;
}
inin(dp, INF), dp[0] = 0;
for (int mk = 1; mk < 1 << n; mk++)
for (int s = mk; s; s = (s - 1) & mk)
tmin(dp[mk], dp[mk ^ s] + sum[s]);
prt(dp[(1 << n) - 1]), putchar('\n');
}
```
---
# 資料結構優化
----
## [Atcoder -- Flowers](https://atcoder.jp/contests/dp/tasks/dp_q)
有 N 朵花排成一列,第 i 朵的高度是 $h_i$、美麗度是 $a_i$,你要選一些花,使得它們的高度
由左至右嚴格遞增,且美麗度總和最大。
$N ≤ 10^6$、$1 ≤ h_i ≤ 10^6$
----
- dp[i]考慮前i個，最後一個選i的答案
- $dp[i]=a_i+max\{dp[j]\ |\ j<i\ \land\ h_j<h_i\}$
- 考慮到 $i$ 時 $j$ 本來就比i小
- 線段樹值域k維護$k=h_j$ 結尾的最大dp值
- 用線段樹轉移，算好dp值更新線段樹
----
程式碼：zkw線段樹看起來很怪
```cpp!
#include <bits/stdc++.h>
#define lowbit(x) ((x) & -(x))
#define eps 1e-9
#define F first
#define S second
#define AC ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
typedef long long llt;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<llt, llt> pll;
signed main()
{
int n, l, r;
llt tp, x;
scanf("%d", &n);
vector<int> hr(n);
for (int i = 0; i < n; i++)
scanf("%d", &hr[i]);
vector<llt> sgt(n << 1, 0);
for (int i = 0; i < n; i++)
{
scanf("%lld", &x), tp = 0;
for (l = n, r = hr[i] + n - 1; l <= r; l >>= 1, r >>= 1)
{
if (l & 1)
tp = max(tp, sgt[l++]);
if (~r & 1)
tp = max(tp, sgt[r--]);
}
x += tp;
for (l = hr[i] + n - 1; l > 0; l >>= 1)
sgt[l] = max(sgt[l], x);
}
printf("%lld\n", sgt[1]);
}
```
----
## 其他應用
- 線段樹可以區間修改，可以logn轉移區間
- 轉移出去可能連續，轉移進來也可能連續
- 根據題目需求決定轉移方向
{"title":"動態規劃","description":"定義dp狀態","contributors":"[{\"id\":\"33757841-f501-406f-a770-4a908423f414\",\"add\":45438,\"del\":4453}]"}