dp入門30題
前言：本文章主要記錄一些 \(dp\) 入門題，都是我做過的，希望讀者能從這些基礎題中打好 \(dp\) 紮實的基礎，有不足的地方也歡迎指出。大部分是 \(CodeFoces\) 和 \(Atcoder\) 的題（可以公開代碼）。
T1：
CF191A
題意：
給你若干字符串，\(a\) 可以拼接到 \(b\) 後面，當且僅當 \(b\) 的最後一個字符與 \(a\) 的第一個字符相同。
舉個栗子：設 \(a,b\) 長度分別為 \(s1,s2\)，則拼接後新的字符串為 \(a+b\)，長度 \(s1+s2\)。
問這樣拼出來得到的字符串第一個字母和最後一個字母相同的字符串的最大長度。
分析：
狀態表示：\(dp(l,r)\) 表示以 \(l\) 開頭，\(r\) 結束的字符串的最大長度。
不難看出，答案就是 \(\max\limits_{i=1}^{26}{dp(i,i)}\)
顯然，轉移只跟字符串長度，開頭元素，末尾元素有關。
則可以寫出狀態轉移方程：\(dp(j,s_{len})=max\{dp(j,s_1)+len\}\)
這裡枚舉轉移的起點 \(j\)，\(s\) 是當前字符串，\(len\) 是串長。
時間複雜度 \(O(26n)\)，空間複雜度 \(O(26^2)\)
Code
T2:
CF455A
題意：
給你一個序列 \(a\)，每次可以選一個 \(x\)，把序列中 \(x-1\) 和 \(x+1\) 刪除，貢獻加 \(x\)，問貢獻的最大值。
分析：
狀態表示：\(dp_i\) 表示算了前 \(i\) 個數（指的是值域）。
正序枚舉，然後這樣就不需要考慮刪除 \(i+1\) 了。
轉移：\(dp_i=max\{dp_{i-2}+num_i \times i,dp_{i-1}\}\)
在刪與不刪中取最大值。
答案：\(dp_{max\{a_i\}}\)
不開 \(long\ long\) 見祖宗！。
Code
T3
CF1061C
題意：
給定一個序列 \(a\)，可以選出一個 \(a\) 的子序列 \(b\)，\(b\) 需要滿足 $ \forall i|b_i $，問有多少個 \(b\) 滿足條件。
分析：
狀態表示：\(dp_{i,j}\) 表示 \(a\) 中前 \(i\) 個數，選了 \(j\) 個數的總方案數。
直接轉移 \(dp_{i,j}+=dp_{i-1,j}\) （轉移 \(1\) ）
當 \(a_i|j\)，則有轉移 \(dp_{i,j}+=dp_{i-1,j-1}\) （轉移 \(2\)）
總的來說就是：\(dp_{i,j}=dp_{i-1,j}+(a[i]\%j==0)\times dp_{i-1,j-1}\)
時間複雜度 \(O(n^2)\)。
然後就歡樂的 $ TLE $ 掉啦。
不難發現，前一維可以用滾動數組優化。
然後又不難發現，\(dp_{i,j}\) 是完全繼承 \(dp_{i-1,j}\)，前面一維可以直接砍掉。
很容易發現，只有 \(j\) 是 \(a_i\) 的因子才會有轉移 \(2\) 。
因此枚舉 $ a_i $ 的因子，然後再轉移，終於就開心的解決啦。
總的來說，就是 \(dp_{b_i}+=dp_{(b_i-1)}\)，\(b_i\) 表示 \(a_i\) 的第 \(i\) 個因子。
時間複雜度 $ O(n\sqrt n) $，空間複雜度 $ O(n) $。
Code
T4
luogu p2289
題意：
有 \(m\) 個任務，每個任務有起始時間，終止時間，和做完任務後得到的價值。做完一個任務後需要休息 \(r\) 的時間才能開始下一個任務，問在總時間 \(n\) 內能得到的最大價值。
分析：
狀態表示：\(dp_i\) 表示前 \(i\) 段時間能夠得到的最多牛奶。
狀態轉移：\(dp_i=max\{dp_i,dp_j+s\}\)
把擠奶時間按左端點最小排序，可以直接轉移。
枚舉第 \(j\) 段任務，看是否滿足條件，然後轉移。
答案：\(max\{dp_i\}\)
時間複雜度 \(O(m^2)\)，空間複雜度 \(O(m^2)\)。
Code
// QwQ
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=1e3+5;
struct pos
{
int l,r,s;
friend bool operator < (pos a,pos b)
{
return a.r<b.r;
}
}e[N];
int n,m,r,dp[N];
int main()
{
scanf("%d %d %d",&n,&m,&r);
for(int i=1;i<=m;i++) scanf("%d %d %d",&e[i].l,&e[i].r,&e[i].s);
sort(e+1,e+1+m);
e[0].r=-1e6;
for(int i=1;i<=m;i++)
for(int j=0;j<i;j++)
if(e[i].l-e[j].r>=r)
dp[i]=max(dp[i],dp[j]+e[i].s);
int ret=0;
for(int i=1;i<=m;i++) ret=max(ret,dp[i]);
printf("%d\n",ret);
return (0-0); // QwQ
}
T5
ABC265E
題意：
你最初在 \((0,0)\)，一共有三種操作，當你在 \((x,y)\)，你可以走到 \((x+a,y+b),(x+c,y+d),(x+e,y+f)\)，一共可以操作 \(n\) 次，有 \(m\) 個點不能走到，問操作 \(n\) 次後能夠走的不同路徑條數。（詳細題目建議見原題，這裡可能說的不太清楚）
分析：
容易發現，路徑只與 \(3\) 種操作的操作次數有關，與先後無關，然後就可以 \(O(n^3)\) 搞了。
狀態表示：\(dp_{i,j,k}\) 表示第一種操作 \(i\) 次，第二種 \(j\) 次，第三種 \(k\) 次能夠走的路徑條數。
狀態轉移：\(dp_{i+1,j,k}+=dp_{i,j,k},dp_{i,j+1,k}+=dp_{i,j,k},dp_{i,j,k+1}+=dp_{i,j,k}\)
答案：\(\sum\limits_{i=0}^{n}\sum\limits_{j=0}^{n-i}\sum\limits_{k=0}^{n-i-j}dp_{i,j,k}\)
時間複雜度 \(O(n^3)\)，空間複雜度 \(O(n^3)\)。
Code
T6
CF414B
題意：
一個數列，後一個數能被前面整除，這個數列就叫做好數列，給定 \(n,k\)，請求出數列長度為 \(k\)，且數列最大值不超過 \(n\) 的好數列個數。
分析：
狀態表示：\(dp_{i,j}\) 表示前 \(i\) 個元素中，第 \(i\) 個數為 \(j\) 的好數列個數。
狀態轉移：\(dp_{i,j}+=dp_{i-1,d}，j|d\)
答案：\(\sum\limits_{i=1}^{n}dp_{k,i}\)
時間複雜度 \(O(\sqrt{n}k^2)\)，空間複雜度 \(O(k^2)\)。
Code
T7
luogu p4310
題意：
給定長度為 \(n\) 數列 \(a\)，求 \(a\) 的子序列 \(b\)，滿足 \(b_i\&b_{i-1}\neq 0,i\geq 2\)，求最長長度 \(b\) 的長度。
分析：
不難發現，\(dp_{i,j}\) 表示在數列 \(a\) 的前 \(i\) 個數中能夠得到的最大長度。有的二進制位有，有的二進制位無，因此這就啟發我們用二進制位作狀態。
狀態表示：\(dp_i\) 表示二進制位 \(i\) 存在時 \(b\) 的長度。
答案：\(\max\{dp_i\}\)
狀態轉移：\(dp_j=max\{dp_k+1\} (j\neq k)\)
時間複雜度 \(O(n)\)，空間複雜度 \(O(30)\)。
Code
// QwQ
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <numeric>
using namespace std;
#define fi first
#define se second
typedef pair<int,int> PII;
typedef long long LL;
template <typename T> void inline read(T& x)
{
x=0; int f=1; char ch;
while((ch=getchar())>'9' || ch<'0') if(ch=='-') f=-1;
while(ch>='0' && ch<='9') x=x*10+(ch^'0'),ch=getchar();
x*=f;
}
int n,dp[35];
int main()
{
read(n);
for(int i=1;i<=n;i++)
{
int x,k=1; read(x);
for(int j=0;j<=30;j++) if(x>>j&1) k=max(k,dp[j]+1);
for(int j=0;j<=30;j++) if(x>>j&1) dp[j]=max(dp[j],k);
}
printf("%d\n",*max_element(dp,dp+31));
return (0-0); // QwQ
}
T8
CF580D
題意：
有 \(n\) 種食物，可以依次選若干種食物，選第 \(i\) 種食物可以獲得 \(a_i\) 價值，有 \(k\) 個條件，\(v_i\)在 \(u_i\) 後選可獲得 \(w_i\) 價值，問共選 \(m\) 種後的最大價值。
分析：
狀態設計：\(dp_{i,j}\) 表示選了狀態為 \(i\) 的食物，當前最後一個選的是 \(j\)。
答案：\(\max\{dp_{i,j}\} (popcount(i)==m \&\& j \in i)\)
狀態轉移：\(dp_{i|(1<<k),k}=\max\{dp_{i,j}+a_k+b_{j,k}\}\ \ (k \notin i)\)
時間複雜度 \(O(n^22^n)\)，空間複雜度 \(O(n2^n)\)。
Code
T9
CF1110D
題意：
有 \(n\) 張牌，每張牌上有一個元素 \(a_i\) 在 \(1\) 到 \(m\) 範圍內，每次可以取出三張牌，牌上元素連續或者相同，每張牌只能用一次，問最多能形成多少個三元組。
分析：
首先，可以肯定是，一定在值域 \(m\) 上做 \(dp\)。
設 \(dp_i\) 表示前 \(i\) 的數字能夠得到的最多三元組數量。
然後發現不能統計 \(i\) 用了多少個，無法轉移。
那就加一維 \(dp_{i,j}\) 表示前 \(i\) 個數字，\([i,i+1,i+2]\) 用了 \(j\) 個 \(i+2\) 得到的最多三元組數量。
這個可以由 \(i-1\) 那一維轉移，但是這隻能知道 \(i+2\) 的個數，不知道 \(i+1,i\)。
再加一維：\(dp_{i,j,k}\)表示前 \(i\) 個數字，\([i,i+1,i+2]\) 用了 \(j\) 個 \(i+2,k\) 個 \(i+1\)，的得到的最多三元組數量。
由於三個 \([i,i+1,i+2]\) 可以看成 \([i,i,i],[i+1,i+1,i+1],[i+2,i+2,i+2]\)。
那麼 \(j,k\) 就是小於 \(3\) 的。
因此得到狀態轉移：\(dp_{i,j,k}=max\{dp_{i-1,k,l}+j+\frac{cnt[i]-j-k-l}{3}\}\)
枚舉 \(j,k,l\)，表示 \(i+2,i+1,i\) 的個數。
答案：$\sum\limits_{j=0}{2}\sum\limits_{k=0}{2}dp_{m,j,k} $
時間複雜度 \(O(27m)\)，空間複雜度 \(O(9m)\)。
Code
特別感謝，wjr 大神的教導。
T10
CF2B
題意：
有一個 \(n\times n\) 的矩形，你需要找到一條路徑，以左上角 \((1,1)\) 為起點，右下角 \(n,n\) 為終點的路徑，使得經過的路徑的點的數字的乘積末尾 \(0\) 個數最少。
每次只能向下或向右走，不能走出矩陣。
分析：
一些數要乘積末尾有 \(0\)，必須保證其中 \(2\) 和 \(5\) 的質因子都大於 \(0\)，因為 \(2\times 5=10\)。
因此第一問只需要求從起點到終點經過的質因子 \(2\) 和 \(5\) 的最少次數，答案取個 \(min\)。
對於第二問，基於第一問，從後向前倒推，找到這個狀態轉移的上一個狀態，遞歸下去。
對於第一問的狀態表示：\(dp_{i,j,0/1}\) 表示走到 \({i,j}\) 經過的質因子 \(2(0),5(1)\) 的最少次數。
狀態轉移：\(dp_{i,j,0/1}=min\{dp_{i-1,j,0/1},dp_{i,j-1,0/1}\}+s_{i,j,0/1}\)
註：此題矩陣中的元素非負，當有 \(0\) 時，走過的路徑數字乘積經過 \(0\) 就變成 \(0\) 了，因此，當第一問答案不為 \(0\) 時，則方案就是從起點到 \(0\) 的位置，再到終點。
時間複雜度 \(O(n^2)\)，空間複雜度 \(O(n^2)\)。
Code
T11
CF4D
題意：
給定序列 \(a,b\)，\(a,b\) 中每個元素有 \(w_i,h_i\)，求出 \(a,b\) 的最長二維上升子序列 \(c\)，保證 \(c\) 中，所有 \(h_i>h_{i-1},w_i>w_{i-1}\)，並且 \(c\) 中 \(w_i>w,h_i>h\)，輸出 \(c\) 的長度和數組 \(c\)。
分析：
首先可以把 \(h_i\leq h\) 或 \(w_i\leq w\) 的捨去。
然後按 \(w_i\) 排序，然後跑一個裸的最長上升子序列。
狀態表示：\(dp_i\) 表示以 \(i\) 結尾的最長上升子序列長度。
狀態轉移：\(dp_i=max\{dp_j+1\}\)，然後記錄轉移的路徑。
第一問答案：\(max\{dp_i\}\)
第二問答案：最大的 \(dp_i\) 的下標 \(i\) 向前遞推。
Code
T12
CF1096D
題意：
給定一個字符串 \(s\)，刪除一個字符有代價，要求刪除一些字符（\(0\) 個也行）使得 \(s\) 中不存在一個子序列為 \(hard\)。
分析：
題目要求子序列不能出現字符串 \(hard\)，不難發現，影響 \(hard\) 是否存在的是 \(har\) 後面是否有 \(d\) ,\(ha\) 後面是否有 \(rd\)，那這就很清楚了。
狀態定義：\(dp_{i,j}\) 表示前 \(i\) 個字符中不存在長度為 \(j\) 的 \(hard\) 的前綴所需要的最小价值。
答案：\(min\{dp_{|s|,j}\},j\in (1,4)\) （我喜歡從 \(1\) 開始計數。）
狀態轉移：考慮一個字符 \(s_i\)，如果他為 \(hard\) 中的字符，那就找到他在 \(hard\) 中的下標，轉移，反之直接繼承。
具體點：\(dp_{i,j}=dp_{i-1,j-(s_i==”hard”_j)}\)
Code
T13
ABC267D
題意：
給定一個序列 \(a\)，需要求出 \(a\) 的一個長度為 \(m\) 子序列 \(b\)，使得 \(\sum\limits_{i=1}^{m}i\times b_i\) 最大。
分析：
可能會有一個錯誤的貪心，只選正數，這是不對的，比如 \(a=\{5,-1,6,1\},m=3\)，貪心會得出答案為 \(20\)（選 \(\{5,6,1\}\)），而實際為 \(21\)（選 \(\{5,-1,6\}\)）。
狀態表示：\(dp_{i,j}\) 表示序列 \(a\) 的前 \(i\) 項中選了 \(m\) 個作為 \(b\) 的最答案。
答案：\(\max\{dp_{i,m}\}\)
狀態轉移：\(dp_{i,j}=max\{dp_{i-1,j-1}+a_i\times j,dp_{i-1,j}\}\)
分別表示將序列 \(a\) 的第 \(i\) 項作為 \(b\) 的第 \(j\) 項和不選。
比較裸，時間複雜度 \(O(nm)\)，空間複雜度 \(O(nm)\)。
Code
T14
ABC267G
題意：
給定序列長度為 \(n\) 的序列 \(a\)，需要求一個長度為 \(m\) 的子序列 \(b\)，使得 \(\sum\limits_{i=1}^{m}i\times b_i\) 最大。
分析：
一個很顯然的狀態設計：\(dp_{i,j}\) 表示前 \(i\) 個數中選了 \(j\) 個的最大價值。
答案：\(\max\limits_{i=1}^{n}dp_{i,m}\)
故有方程：\(dp_{i,j}=max\{dp_{i-1,j},dp_{i-1,j-1}+j\times a_i\}\)
Code
T15
CF1207C
題意：
城市裡正在修軌道和支柱，分別花費 \(a,b\)。給定長度 \(n\) 的 \(01\) 序列，如果某一位為 \(1\) 表示這段軌道要通車，反之不需要，通車必須滿足軌道高度大於等於 \(2\)。要保證所有通車高度為 \(2\) 的同時，修軌道和支柱花費最小。（更多細節請參見原題）。
分析：
貪心方面想，在通車階段一定是要貢獻 \(a+2b\)，這是毋庸置疑的，主要就是通車不通車交匯處，你要考慮他是保持高度為 \(2\) 還是降到 \(1\)。然後發現如果貪心，應該可以做，但是細節有點多，不好實現，因此考慮 \(dp\)。
狀態表示：\(dp_{i,0/1}\) 表示第 \(i\) 段高度為 \(1(0),2(1)\) 時的最下花費。
答案： \(\min\{dp_{n,0}+b,dp_{n-1,1}+2\times (a+b)\}\)。 最後到終點高度為 \(1\)。
狀態轉移：\(\begin{cases}dp_{i,0}=min\{dp_{i-1,0}+a+b,dp_{i-1,1}+2\times (a+b)\}\\
dp_{i,1}=min\{dp_{i-1,0}+2\times a+b,dp_{i-1,1}+a+2\times b\}\end{cases}\)
對於通車段，只能從高度為 \(2\) 轉移，而高度為 \(1\) 是做不到的，因此 \(dp_{i,0}\) 賦值正無窮，\(dp_{i,1}=dp_{i-1,1}+a+2\times b\)
時間複雜度 \(O(n)\)，空間複雜度 \(O(n)\)。
Code
T16
CF1625C
題意：
有兩座城市 \(A,B\)，距離為 \(L\)，沿途有 \(n\) 個標識，第 \(i\) 個離 \(A\) 距離 \(d_i\)。表示從這裡開始，速度不能超過 \(a_i\)。保證起點有標識，即 \(d_1=0\)。
現在可以移去其中至多 \(k\) 個標識，使 \(A\) 到 \(B\) 時間最短，輸出時間。
分析：
這種題，看完第一想到的肯定是 \(dp\)，蠻經典的。
狀態表示：\(dp_{i,j}\) 表示走到第 \(i\) 個標識，移去了其中 \(j\) 個的最短花費時間。
狀態轉移：\(dp_{i,j}=min\{dp_{i-o-1,j-o}+(d_i-d_{i-o-1})\times a_{i-o-1}\}\)
解釋一下，很顯然，枚舉連續去掉了多少個標識(\(o\))，這樣是顯然並且正確的，轉移看起來就很正確。
易錯：最後一個標識位置可能不為 \(L\)，因此還需要多開一個點，保證一定能到終點。
答案：\(min\{dp_{n+1,i}\},i\leq k\)。
時間複雜度 \(O(nk^2)\)，空間複雜度 \(O(nk)\)。
Code
T17
CF1105C
題意：
你需要構造長度為 \(n\) 的序列，序列中的每一項值在 \([l,r]\) 中，要使序列元素總和為 \(3\) 的倍數，有多少種方案。
分析：
由於序列元素總和為 \(3\) 的倍數，那麼只需要維護當前序列元素和模 \(3\) 的餘數，有多少種即可。
因此可得狀態表示：\(dp_{i,j}\) 表示當前序列長度為 \(i\)，序列元素和模 \(3\) 的餘數為 \(j\)。
答案：\(dp_{n,0}\)
這裡需要記錄 \([l,r]\) 中，模 \(3\) 的餘數為 \(0,1,2\) 的分別有多少，比較簡單，兩頭判斷，中間直接算即可。
狀態轉移：\(\begin{cases}dp_{i,0}=dp_{i-1,0}\times s_0+dp_{i-1,1}\times s_2+dp_{i-1,2}\times s_1\\dp_{i,1}=dp_{i-1,0}\times s_1+dp_{i-1,1}\times s_0+dp_{i-1,2}\times s_2\\dp_{i,2}=dp_{i-1,0}\times s_2+dp_{i-1,1}\times s_1+dp_{i-1,2}\times s_0\end{cases}\)
其實可以通過一些運算循環簡化，但是這樣寫更易懂。
Code
T18
CF1743C
題意：
給定一個長度為 \(n\) 的序列 \(a\) 和字符串 \(s\)，對於字符串的第 \(i\) 位，如果 \(s_i\) 為 \(1\)，表示可以將答案貢獻增加 \(a_{i-1}\) 或 \(a_i\)。問最大貢獻。
分析：
此題可以貪心，但既然是 \(dp\) 專題，當然是介紹 \(dp\) 做法。
發現這個題只有兩種狀態，第 \(i\) 位是否有貢獻。
因此有狀態表示：\(dp_{i,0/1}\) 表示第 \(i\) 位選/不選的最大貢獻。
狀態轉移：\(\begin{cases}dp_{i,0}=dp_{i-1,0}+a_{i-1},dp_{i,1}=max\{dp_{i-1,0},dp_{i-1,1}\}+a_i\ \ \ \ (s_i==1)\\dp_{i,0}=dp_{i,1}=max\{dp_{i-1,0},dp_{i-1,1}\}\ \ \ \ (s_i==0)\end{cases}\)
答案：\(min\{dp_{i,0},dp_{i,1}\}\)
時間複雜度 \(O(n)\)，空間複雜度 \(O(n)\)。
Code
T19
CF118D
題意：
給定一個 \(01\) 序列，請求出其中 \(0,1\) 的個數分別為 \(n0,n1\) 且最長的連續的 \(0\) 長度不超過 \(k1\)，最長的連續 \(1\) 的長度不超過 \(k2\) 的序列個數。
輸出答案對 \(10^8\) 取模。
分析：
應該是比較顯然的狀態表示：\(dp_{i,j,k,0/1}\) 表示用了 \(i\) 個 \(0\),\(j\) 個 \(1\)，當前末尾 \(0/1\) 有 \(k\) 個連續。
答案：\(\sum\limits_{i=1}^{k0}dp_{n0,n1,i,0}+\sum\limits_{i=1}^{k1}dp_{n0,n1,i,1}\)
狀態轉移：\(\begin{cases}dp_{i,j,k,s}+=dp_{i-1,j,k-1,s}\\dp_{i,j,1,s}+=dp_{i-1,j,k,s\bigoplus 1}\end{cases}\)
\(s\) 表示當前末尾是 \(0/1\)，方程都是一樣的，\(0/1\) 交換一下就行了，注意邊界。
Code
T20
CF467C
題意：
給定一個長度為 \(n\) 的序列 \(a\)，需要求出他 \(m\) 個互不相交的長度為 \(k\) 的子串，權值最大，保證一定有解。
分析：
狀態表示：\(dp_{i,j}\) 表示前 \(i\) 個數中，選出了 \(j\) 個子串的最大權值。
答案：\(dp_{n,m}\)
狀態轉移：\(dp_{i,j}=max\{dp_{i-1,j},dp_{i-m,j-1}+(s_i-s_{i-m}) (i \geq m)\}\)
Code
T21
CF706C
題意：
給定若干字符串，可以選擇若干字符串，將他們翻轉，花費為 \(a_i\)，問使得所有字符串不降序排序最小花費，不可能輸出 \(-1\)。
分析：
不難發現，每個字符串是否需要翻轉，只與上一個字符串有關，那麼狀態表示：\(dp_{i,0/1}\) 第 \(i\) 個字符串是否翻轉。
記 \(s1\) 表示 \(s\) 翻轉後的字符串。
狀態轉移：\(\begin{cases}dp_{i,0}=min\{dp_{i-1,0}\} \ \ \ \ s_i\geq s_{i-1}\\dp_{i,0}=min\{dp_{i-1,1}\} \ \ \ \ s_i\geq s1_{i-1}\\dp_{i,1}=min\{dp_{i-1,0}+a_i\} \ \ \ \ s1_i\geq s_{i-1}\\dp_{i,1}=min\{dp_{i-1,1}+a_i\} \ \ \ \ s1_i\geq s1_{i-1}\end{cases}\)
答案：\(min\{dp_{n,0},dp_{n,1}\}\)
時間複雜度 \(O(n)\)，空間複雜度 \(O(n)\)。
Code
T22
CF431C
題意：
有一棵滿 \(k\) 叉樹，樹的每條邊都有權值，每個非葉子節點指向 \(k\) 個兒子的邊權分別為 \(1,2,3…k\)。請求出從根節點開始一直向下走到葉子節點，所經過的邊權值和為 \(n\) 且其中至少一條邊大於等於 \(d\) 的總方案數。
答案對 \(10^9+7\) 取模。
分析：
因為題目只要求至少一條邊大於等於 \(d\)，因此直接設狀態 \(dp_{i,j}\) 當前邊權和 \(i\) 且當前邊權值為 \(j\)，然後發現，有多條邊權值和大於等於 \(d\) 會被重複統計。
因此轉換狀態表示：\(dp_{i,0/1}\) 表示當前邊權和為 \(i\)，且當前是否存在邊權大於等於 \(d\) 的點的方案數。
狀態轉移：\(\begin{cases}dp_{i,0}+=dp_{i-j,0}\ \ \ \ (j<d)\\dp_{i,1}+=dp_{i-j,0}\ \ \ \ (j\geq d)\\dp_{i,1}+=dp_{i-j,1}\end{cases}\)
答案：\(dp_{n,1}\)
Code
T23
CF607A
題意：
有 \(n\) 個激光塔排成一行，第 \(i\) 個的位置是 \(a_i\)(\(a_i\) 單調遞增)，威力是 \(b_i\)。當第 \(i\) 個激光塔被激活，所有這個激光塔左邊的與他舉例小於等於 \(b_i\) 的激光塔會被摧毀，發出激光的激光塔不會被摧毀。現在從右向左一次開啟沒有被摧毀的激光塔。
你現在可以在第 \(n\) 個激光塔右邊任意放置一個激光塔，問如何安排這個機關塔使得被摧毀的激光塔數量最少。
分析：
這題我想了好久，但還是擺了。
本題有個很顯然的暴力，枚舉最右邊被摧毀的激光塔個數，再模擬一遍可以得出答案。
但複雜度是 \(O(n^2)\) 的，顯然不能接受。
狀態表示：\(dp_i\) 表示從位置 \(i\) 開始啟動激光，能保留激光塔的最大個數，然後可以遞推。
為了方便，我們記 \(v_i\) 表示位置 \(i\) 的激光威力值，\(v_i==0\) 表示此處沒有激光塔。
方程：\(dp_i=\begin{cases}dp_{i-1}\ \ \ \ (v_i==0)\\dp_{i-v_i-1}+1\ \ \ \ (i-v_i-1 \geq 0)\\1\end{cases}\)
答案：\(n-\min\limits_{i=0}^{len}dp_i\)
Code
T24
CF1475G
題意：
給定 \(n\) 個數，選出若干個數，使得這若干個數中任意兩個數，有一個是另一個的倍數，最大化選數個數（最小化刪數個數）。
分析：
因為貪心無法維護，所以使用動態規劃。
狀態表示：\(dp_i\) 表示不超過 \(i\) 的數的最大選數個數，容易發現，轉移只與他的倍數有關，然後就可以枚舉他的倍數 \(j\)。
則有方程：\(dp_j=max\{dp_i,dp_j\}\)
答案就是 \(n-max\{dp_i\}\)。
\(dp_i\) 初始化為 \(cnt_i\) 表示 \(i\) 出現的次數。
Code
T25
CF1249E
題意：
給定 \(n,c\)，一棟樓有 \(n\) 層，上電梯（加等待時間）需要 \(c\)，走樓梯上一層樓時間 \(a_i\)，坐電梯上一層樓時間 \(b_i\)，問到達每一層樓最少需要的時間。
分析：
狀態機模板。
狀態表示：\(dp_{i,0/1}\) 表示在第 \(i\) 層，從 \(i-1\) 到 \(i\) 層是走樓梯 (\(0\)) 還是坐電梯 (\(1\)) 的最小時間。
狀態轉移：\(\begin{cases}dp_{i,0}=min\{dp_{i-1,0},dp_{i-1,1}\}+a_i\\dp_{i,1}=min\{dp_{i-1,0}+c,dp_{i-1,1}\}+b_i\end{cases}\)
初始化 \(dp_{1,1}=c+a_1\)
第 \(i\) 層答案 \(min\{dp_{i,0},dp_{i,1}\}\)
Code
T26
CFABC275E
題意：
給定 \(n,m,k\)，一個棋盤有 \(n+1\) 個格子，編號為 \(0,1…n\)，剛開始你在 \(0\)，然後可以投 \(k\) 次骰子，在 \([1,m]\) 中等概率的投到 \(s\)，走 \(s\) 步（如果當前位置編號大於 \(n\)），則多走的距離，你需要往回退（飛行棋都玩過吧）。求到終點 \(n\) 的期望。
答案對 \(998244353\) 取模。
分析：
考慮 \(n,m,k\) 都比較小，設 \(dp_{i,j}\) 表示投了 \(i\) 次骰子，當前在 \(j\) 的期望。
然後很容易發現，每次投骰子，每一面都有 \(\frac{1}{m}\) 的概率得到，分母就是 \(\frac{1}{m}\)。
設 \(pv\) 表示 \(m\) 在模 \(998244353\) 下的逆元。
枚舉投的次數 \(i\)，上一次的位置 \(j\)，投到了數字 \(o\)，那麼有轉移。
\(\begin{cases} dp_{i,j+o}+=pv\cdot dp_{i-1,j}\ \ \ \ (j+o<n)\\dp_{i,n-(j+o-n)}+=pv\cdot dp_{i-1,j}\ \ \ (j+o>n)\end{cases}\)
初始化 \(dp_{0,0}=1\)
答案 \(\sum\limits_{i=1}^{k}dp_{i,n}\)
時間複雜度 \(O(nmk)\)，空間複雜度 \(O(nk)\)
Code
T27
CF1324E
題意：
一天有 \(h\) 小時，現在是 \(0\) 小時，你將會睡 \(n\) 次覺，每次可以選擇睡 \(a_i\) 小時或 \(a_i-1\) 小時，當開始睡覺的那個小時 \(x\) 在 \([l,r]\) 中，那麼這次睡眠是優秀的，求優秀睡眠次數最大次數。
分析：
每次睡覺有兩種選擇，當要睡覺時，並不知道當前睡覺時間，但卻只與上次睡覺開始時間，時長有關，具有無後效行，考慮 \(dp\)。
狀態表示：\(dp_{i,j}\) 表示第 \(i\) 次睡眠，開始睡覺的時間是 \(j\) 的優秀睡眠最大次數。
狀態轉移：\(dp_{i,j} = dp_{i-1,(j-a_i+h)\%h},dp_{i-1,(j-a_i-1+h)\%h}+(j\geq l\ \&\&\ j\leq r)\)
答案：\(\sum\limits_{i=0}^{h}dp_{n,i}\)
Code
T28
CF163A
題意：
給定字符串 \(a,b\)，求 \(a\) 的子串 \(x\)，\(b\) 的子序列 \(y\) 相等的個數。
答案對 \(10^9+7\) 取模。
分析：
直接設狀態，感覺不好分析出狀態，類比最長公共子序列。
狀態表示：\(dp_{i,j}\) 表示 \(a\) 中以 \(i\) 結尾的子串，\(b\) 中以 \(j\) 結尾的子序列，滿足題意的串個數。
轉移方程：\(dp_{i,j} = dp_{i,j-1}+[a_i==b_j]\times (dp_{i-1,j-1}+1)\)
答案：\(\sum\limits_{i=1}^{n}dp_{i,|b|}\)
Code
T29
CF106C
題意：
有 \(n\) 克麵糰和 \(m\) 種不同餡料，第 \(i\) 種餡料有 \(a_i\) 克，做一個第 \(i\) 種麵包，需要 \(b_i\) 克第 \(i\) 種餡料，\(c_i\) 克麵糰，這種麵包一個賣 \(d_i\)。
當做沒有餡料的麵包，需要 \(c_0\) 克麵糰，可賣 \(d_0\)。
現在你需要求出在麵糰和餡料都夠的情況下。能改賣的最大價值。
分析:
此題應該用背包解決。
狀態表示：\(dp_{i,j}\) 表示用前 \(i\) 種餡料做麵包，用了 \(j\) 克麵糰能夠獲得的最大價值。
答案：\(\max\limits_{i=0}^{n}dp_{m,i}+\left\lfloor\frac{(n-i)}{c_0}\right\rfloor\times d_0\)
分別枚舉 \(i,j,k\) 表示第 \(i\) 種餡餅，當前用了 \(j\) 克麵糰，第 \(i\) 種餡餅用了 \(k\) 個。
狀態轉移：\(dp_{i,j}=max\{dp_{i-1,j-c_i\times k}+d_i\times k\}\)
Code
T30
CF1051D
題意：
有一個 \(2\times n\) 的網格，要在網格中填入黑塊和白塊，使得網格中恰好有 \(m\) 個連通塊，求方案數。
答案對 \(998244353\) 取模
分析：
考慮到這是個 \(2\times n\) 的網格，填入的塊狀態有限，可以直接把每一列的塊寫入狀態。
因此有方程 \(dp_{i,j,k} (k \in [0,3])\) 表示前 \(i\) 列中，共有 \(j\) 個連通塊，第 \(i\) 列的狀態是 \(k\)。
答案：\(\sum\limits_{i=0}^{3}dp_{n,m,i}\)
我這裡設塊的狀態為：
\(0\ \ 1\ \ \ 2\ \ 3\)
\(W W B B\)
\(W B W B\)
轉移也比較明顯：
\(\begin{cases}dp_{i,j,0}=dp_{i-1,j,0}+dp_{i-1,j,1}+dp_{i-1,j,2}+dp_{i-1,j-1,3}\\dp_{i,j,1}=dp_{i-1,j-1,0}+dp_{i-1,j,1}+dp_{i-1,j-2,2}+dp_{i-1,j-1,3}\\dp_{i,j,2}=dp_{i-1,j-1,0}+dp_{i-1,j-2,1}+dp_{i-1,j,2}+dp_{i-1,j-1,3}\\dp_{i,j,3}=dp_{i-1,j-1,0}+dp_{i-1,j,1}+dp_{i-1,j,2}+dp_{i-1,j,3}\end{cases}\)
