动态规划100题 1~10 题
FjswYuzu
·
·
个人记录
1.「NOI2001」炮兵阵地（简单状压 dp）
$\ \ \ \ \ \ \ $首先观察题目，我们发现不能用传统的方式去定义我们的 dp 数组，因为 $dp_{i,j}$ 甚至维度更高似乎无法有效地储存状态。并且我们的影响范围还会影响到前两行，怎么办呢？
$\ \ \ \ \ \ \ $我们发现 $n,m$ 都是很小的，炮兵影响范围相对来说也是比较小的。我们考虑状压 dp。首先我们定义一行炮兵排列合法，当且仅当炮兵互相之间不冲突，并且炮兵不会放置在山上。于是我们考虑在 dp 数组之间带上前 1 行的状态和当前行状态。为什么不考虑前两行呢？是因为我们转移的时候，确定前 1 行合法，那么前 2 行会被当做前 1 行的前 1 行处理掉。
$\ \ \ \ \ \ \ $我们考虑如何保存状态。我们将状态压缩成一个数 $S$。这个 $S$ 转化成二进制，如果第 $x$ 位是 1，就代表第 $x$ 位有炮兵。
$\ \ \ \ \ \ \ $根据上面，我们可以很自然地定义出 $dp_{i,S,T}$ 为第 $i$ 行状态为 $S$，$i-1$ 行状态为 $T$ 的放置最多炮兵数。有 dp 方程：
$$dp_{i,S,T}=\max \{ dp_{i-1,T,U} \}$$
$\ \ \ \ \ \ \ $其中 $i,S,T$ 如上定义，$U$ 即为 $i-2$ 行的状态。其中满足:
- $S \& T=0$。
- $S \& U=0$。
- $T \& U=0$。
- $S,T,U$ 都合法。
- $3 \leq i \leq n$.
$\ \ \ \ \ \ \ $有了这些，很容易得到我们的答案即为 $\sum dp_i,S,T$。其中 $i,S,T$ 需要枚举计算答案。
$\ \ \ \ \ \ \ $同时，我们需要预处理。我们从第 1 行开始。如果这一行选择状态 $K$ 是可以的，那么我们的 $dp_{1,K,0}=|K|$，其中 $|K|$ 为 $K$ 转化成二进制之后有多少个 1。计算这个东西有两种方法：
```cpp
int __builtin_popcount(int x);
long long __builtin_popcountll(long long x);
```
$\ \ \ \ \ \ \ $内置函数，可直接使用，但是很慢。。。最好别用。
```cpp
int lowbit(int x){return x&(-x);}
int popcount(int x)
{
int ans=0;
while(x)
{
x-=lowbit(x);
++ans;
}
return ans;
}
```
$\ \ \ \ \ \ \ $预处理 $dp_2$ 也是很简单的，仍然是枚举计算。
$\ \ \ \ \ \ \ $我们的时间复杂度 $O(n \times 2^{3m})$。但实际上加上我们不合法序列的剪枝，跑的会快很多。但是这道题卡空间。。。
$\ \ \ \ \ \ \ $我们发现我们的状态只跟前两行有关，于是我们可以把第一位滚掉，就不会 MLE 了。
```cpp
#include<cstdio>
#include<algorithm>
#define BuiPop(i) __builtin_popcount(i)
#define last j
#define now k
#define lastslast l
using namespace std;
int dp[3][1025][1025],a[105],n,m,ans;
char c[15];
void Prepare()
{
for(int i=0;i<(1<<m);++i) if(!(i&(i<<1) || i&(i<<2) || i&a[1])) dp[1][i][0]=BuiPop(i);
for(int i=0;i<(1<<m);++i) for(int j=0;j<(1<<m);++j) if(!(i&j || i&(i<<1) || i&(i<<2) || j&(j<<1) || j&(j<<2) || i&a[1] || j&a[2])) dp[2][j][i]=BuiPop(i)+BuiPop(j);
}
void DynamicProgramming()
{
for(int i=3;i<=n;++i)
{
for(int j=0;j<(1<<m);++j)//last
{
if(j&(j<<1) || j&(j<<2) || j&a[i-1]) continue;
for(int k=0;k<(1<<m);++k)//now
{
if(j&k || k&(k<<1) || k&(k<<2) || k&a[i]) continue;
for(int l=0;l<(1<<m);++l)//last's last
{
if(l&j || l&k || l&(l<<1) || l&(l<<2) || l&a[i-2]) continue;
dp[i%3][now][last]=max(dp[i%3][now][last],dp[(i-1)%3][last][lastslast]+BuiPop(k));
}
}
}
}
}
void GetAnswers()
{
for(int i=0;i<(1<<m);++i) for(int j=0;j<(1<<m);++j) ans=max(ans,dp[n%3][i][j]);
}
int main(){
scanf("%d %d",&n,&m);
for(int i=1;i<=n;++i)
{
scanf("%s",c+1);
for(int j=1;j<=m;++j)
{
a[i]<<=1;
if(c[j]=='H') a[i]|=1;
}
}
Prepare();
DynamicProgramming();
GetAnswers();
printf("%d",ans);
return 0;
}
```
## 2.「JSOI2016」病毒感染（dp 预处理拆开复杂度处理）
$\ \ \ \ \ \ \ $[luogu](https://www.luogu.com.cn/problem/P5774)
$\ \ \ \ \ \ \ $算是一道简单的 dp 题了。
$\ \ \ \ \ \ \ $我们直接暴力 dp 会发现 $O(n^3)$ 的时间复杂度只能得 $50\%$ 的分，于是我们考虑优化。
$\ \ \ \ \ \ \ $瓶颈在于我们无法快速计算 $i → j → i$ 途中的最少死亡的人数。于是我们把两样东西拆开来进行计算。
$\ \ \ \ \ \ \ $因为村庄排成一条链，我们定义 $sum_i=\sum_{j=1}^i a_j$。
$\ \ \ \ \ \ \ $我们定义 $dp_{i,j}$ 为 $i → j → i$ 途中的最少死亡的人数，枚举 $i$ 为起点， $j$ 为长度，可以得到这个 dp 方程：
$$dp_{j,i+j}=dp_{j+1,i+j} + \min ((sum_{i+j}-sum_{j})\times 2 , a_j \times i \times 3 + sum_{i+j}-sum_{j})$$
$\ \ \ \ \ \ \ $至此，我们用 $O(n^2)$ 的时间复杂度完成了预处理，接下来就是计算答案。
$\ \ \ \ \ \ \ $我们定义 $dp2_i$ 为当前在村庄 $i$ 并且 $i$ 到 $i$ 以前的村庄疫情消灭的总消失最小人数，我们可以快速得到：
$$dp2_i=\min \{dp2_j+dp_{j+1,i}+(4 \times i - 4 \times j - 2)\times (sum_n-sum_i)\}$$
$\ \ \ \ \ \ \ $至此，时间复杂度 $O(n^2)$，可以解决问题。
```cpp
#include<cstdio>
#include<cstring>
long long min(long long x,long long y){return x<y?x:y;}
long long n,dp[3005][3005],dp2[3005],sum[3005],a[3005];
int main(){
scanf("%lld",&n);
for(long long i=1;i<=n;++i) scanf("%lld",&a[i]),sum[i]=sum[i-1]+a[i];
for(long long i=1;i<=n-1;++i) for(long long j=1;j<=n-i;++j) dp[j][i+j]=dp[j+1][i+j]+min((sum[i+j]-sum[j])*2,a[j]*i*3+sum[i+j]-sum[j]);
memset(dp2,0x3f,sizeof dp2);//设置极大值
dp2[0]=0;
for(long long i=1;i<=n;++i) for(long long j=0;j<i;++j) dp2[i]=min(dp2[i],dp2[j]+dp[j+1][i]+(4*i-4*j-2)*(sum[n]-sum[i]));
printf("%lld",dp2[n]);
return 0;
}
```
## 3.「ZJOI2007」棋盘制作（dp + 单调栈经典模型）
$\ \ \ \ \ \ \ $[luogu](https://www.luogu.com.cn/problem/P1169)
$\ \ \ \ \ \ \ $我们要找到一个黑白相间的棋盘（可以参考国际象棋棋盘），第一个小问题是找到最大的正方形，第二个是找到最大的矩形。
$\ \ \ \ \ \ \ $我们注意到棋盘跟题 1 一样只有两种格子，能用状压吗？答案是否。因为 $n,m \leq 2000$，所以不能状压。
$\ \ \ \ \ \ \ $同时，找到最大的合法正方形和矩形，恰好是我们的找纯色最大正方形和矩形的经典模型（分别用 dp 和单调栈求解），我们能够在此间转换吗？
$\ \ \ \ \ \ \ $答案是可以的。我们将 $a_{i,j} \oplus 1 (i + j \mod 2 = 0)$，其中 $\oplus$ 为异或符号。
$\ \ \ \ \ \ \ $我们发现随机取上一个矩阵，我们翻转了之后，发现其实就是可以互相转换的。现在我们反转之后只需要求纯色最大正方形和矩形的经典模型了。
$\ \ \ \ \ \ \ $对于第一个问题，定义 $dp_{0,i,j}$ 为 $a_{i,j}=0$，以 $(i,j)$ 为右下角的正方形最大边长。$dp_1$ 同理。对于 dp 方程，有：
$$\begin{cases}
dp_{0,i,j}=\min \{ dp_{0,i-1,j},dp_{0,i-1,j-1},dp_{0,i,j-1}+1\} (a_{i,j}=0) \\ dp_{1,i,j}=\min \{ dp_{1,i-1,j},dp_{1,i-1,j-1},dp_{1,i,j-1}+1\} (a_{i,j}=1)
\end{cases}$$
$\ \ \ \ \ \ \ $易得答案为 $\max \{ dp \}$，时间复杂度 $O(nm)$。
$\ \ \ \ \ \ \ $对于第二个问题，用单调栈求解。我们首先储存一段连续的高，也就是对于一个数最多能往上延伸多少相同的连续的数。枚举每一行作为矩形底边，这道题就变成了直方图最大矩形问题。枚举下边时间复杂度 $O(n)$，单调栈 $O(m)$。
$\ \ \ \ \ \ \ $得到这些，总时间复杂度 $O(nm)$，可以通过题目。感谢 S-LJS 搬运到校OJ。公开之后会发链接。
$\ \ \ \ \ \ \ $代码如下。
```cpp
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m,a[2005][2005];
namespace DynamicProgramming
{
int dp1[2005][2005],dp2[2005][2005];
void Dp()
{
int ans=0;
for(int i=1;i<=n;++i)
{
for(int j=1;j<=m;++j)
{
if(a[i][j]) dp1[i][j]=min(min(dp1[i-1][j],dp1[i][j-1]),dp1[i-1][j-1])+1;
else dp2[i][j]=min(min(dp2[i-1][j],dp2[i][j-1]),dp2[i-1][j-1])+1;
ans=max(ans,max(dp1[i][j],dp2[i][j]));
}
}
printf("%d\n",ans*ans);
}
}
namespace MonotonicStack
{
int cnt[2005][2005],ans,s[2005],l[2005];
void Monotonic(int sp[])
{
int top=0,len=0;
s[top]=l[top]=0;
for(int i=1;i<=m;++i)
{
if(sp[i]>=s[top]) s[++top]=sp[i],l[top]=1;
else
{
len=0;
while(top && s[top]>sp[i])
{
len+=l[top];
ans=max(ans,len*s[top]);
--top;
}
s[++top]=sp[i];
l[top]=len+1;
}
}
len=0;
while(top)
{
len+=l[top];
ans=max(ans,len*s[top]);
--top;
}
}
void Stack(){for(int i=1;i<=n;++i) Monotonic(cnt[i]);}
void Ans(){printf("%d",ans);}
}
using namespace MonotonicStack;
int main(){
scanf("%d %d",&n,&m);
for(int i=1;i<=n;++i)
{
for(int j=1;j<=m;++j)
{
scanf("%d",&a[i][j]);
if(!((i+j)&1)) a[i][j]^=1;
if(a[i][j]) cnt[i][j]=cnt[i-1][j]+1;
}
}
DynamicProgramming::Dp();
MonotonicStack::Stack();
memset(cnt,0,sizeof cnt);
for(int i=1;i<=n;++i)
{
for(int j=1;j<=m;++j)
{
if(!a[i][j]) cnt[i][j]=cnt[i-1][j]+1;
}
}
MonotonicStack::Stack();
MonotonicStack::Ans();
return 0;
}
```
## 4.「SEERC2019」Game on a Tree（博弈论类树形 dp）
$\ \ \ \ \ \ \ $[luogu](https://www.luogu.com.cn/problem/P5801)
$\ \ \ \ \ \ \ $题意转化：有一棵以 1 为根的树，每个节点的初始颜色为白色。Alice 先让任意一个节点放上标记变黑作为一次操作。然后 Bob 开始，轮流移动这个标记到当前所在节点的任意一个白色的祖先或者后代节点，并且把它这个节点染成黑色。谁不能移动谁就输了。
$\ \ \ \ \ \ \ $考虑这个树上博弈问题。首先引进树的最大匹配。不会的同学，可以自查博客。
$\ \ \ \ \ \ \ $首先假设我们只能够走到相邻的节点，我们发现我们只需要判断这棵树是否满足，它的最大匹配是一个完美匹配。如果是的话，后手必胜，否则先手一定能够避免，于是先手必胜。
$\ \ \ \ \ \ \ $回到问题，我们不只是走到相邻的节点。但是思路相同，这个问题我们用树形 dp 求解。
$\ \ \ \ \ \ \ $定义 $dp_i$ 为节点 $i$ 以及该节点对应子树未匹配节点的最小数量，$cnt=\sum_{\texttt{以i为根节点的后代j}} dp_j
dp_i = cnt - 1 (cnt > 0), \\ dp_i = 1 (cnt = 0). \\
\end{cases}
```cpp
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
vector<int> G[100005];
int dp[100005],n;
bool vis[100005];
void dfs(int now,int pre)
{
bool flag=false;
for(unsigned int i=0;i<G[now].size();++i)
{
if(G[now][i]==pre) continue;
dfs(G[now][i],now);
flag|=vis[G[now][i]];
dp[now]+=max(dp[G[now][i]],vis[G[now][i]]?1:0);
}
if(!flag || dp[now]>0) vis[now]=true;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n-1;++i)
{
int x,y;
scanf("%d %d",&x,&y);
G[x].push_back(y);
G[y].push_back(x);
}
memset(dp,-1,sizeof dp);
dfs(1,0);
puts(dp[1]?"Alice":"Bob");
return 0;
}
```
## 5.「NOI1997」积木游戏（较难的线性 dp）
$\ \ \ \ \ \ \ $[luogu](https://www.luogu.com.cn/problem/P5760)
$\ \ \ \ \ \ \ $我们定义 $dp_{i,j,k}$ 为前 $i$ 个积木垒成 $j$ 堆，并且当前正在处理第 $k$ 个平面。$0 \leq k \leq 2$，分别代表积木不同的三面。
$\ \ \ \ \ \ \ $我们很容易发现我们可以再多垒成一堆，也可以搭在当前这一堆积木上面。但是一定要注意再新垒成一堆的话就不用判断之前的积木的长宽高了。
$\ \ \ \ \ \ \ $我们能够很顺利地推出我们的转移方程：
$$dp_{i,j,pm}=\max \{dp_{i-1,k,Last}+buf \}$$
$\ \ \ \ \ \ \ $如果还可以垒到当前的积木上面去：
$$dp_{i,j,pm}=\max \{{dp_{i,k,Last}+buf} \}$$
$\ \ \ \ \ \ \ $其中 $i,j$ 意义如上，$k$ 为当前选到要搭上的积木，$pm$ 为当前平面，$Last$ 为上个平面。
```cpp
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<queue>
using namespace std;
int n,m,a[105],b[105],c[105],dp[105][105][3];//dp[i][j][k]：前i个堆垒j个正在处理k平面
int main(){
scanf("%d %d",&n,&m);
for(int i=1;i<=n;++i) scanf("%d %d %d",&a[i],&b[i],&c[i]);//进行输入
for(int i=1;i<=m;++i)
{
for(int j=1;j<=n;++j)
{
for(int k=0;k<j;++k)
{
for(int pm=0;pm<=2;++pm)
{
int x,y,buf;
if(pm==0) x=a[j],y=b[j],buf=c[j];
if(pm==1) x=b[j],y=c[j],buf=a[j];
if(pm==2) x=c[j],y=a[j],buf=b[j];
if(x<y) x^=y^=x^=y;
for(int Last=0;Last<=2;++Last)
{
int xx,yy;
if(Last==0) xx=a[k],yy=b[k];
if(Last==1) xx=b[k],yy=c[k];
if(Last==2) xx=c[k],yy=a[k];
if(xx<yy) xx^=yy^=xx^=yy;
dp[i][j][pm]=max(dp[i][j][pm],dp[i-1][k][Last]+buf);
if(x>xx || y>yy) continue;
dp[i][j][pm]=max(dp[i][j][pm],dp[i][k][Last]+buf);
}
}
}
}
}
int ans=-10086001;
for(int i=1;i<=n;++i) ans=max(ans,max(max(dp[m][i][0],dp[m][i][1]),dp[m][i][2]));
printf("%d",ans);
return 0;
}
```
## 6.「HAOI2006」数字序列（很牛逼的线性 dp + 数学证明）
$\ \ \ \ \ \ \ $[luogu](https://www.luogu.com.cn/problem/P2501)
$\ \ \ \ \ \ \ $dp 一步走，简化题意。也就是说改变一个序列里面的某些元素使得序列严格单调上升，并且修改元素最少。在满足上一个情况下，我们改变元素的幅度最小，也就是 $\sum _{i=1} ^n |a_i-fix_i|$ 最小。
$\ \ \ \ \ \ \ $但是我们如何确定修改元素最少呢？似乎没有很显然的方法。于是我们考虑使不修改元素尽量多，也就可以让我们有 dp 思路。
$\ \ \ \ \ \ \ $两个元素不修改的必要条件，当且仅当 $a_i,a_j(1 \leq i \le j \leq n)$，满足 $a_i+j-i \leq a_j$。转化之后得到 $a_i-i \leq a_j-j$。我们将所有的 $a_i-i$，第一个小问题就转化成了当前 $a$ 序列的 $LIS$。注意用 $O(n \log n)$ 的方法去转化。这里得到的 dp 值下文记为 $f_i$。
$\ \ \ \ \ \ \ $考虑第二个子问题。我们定义 $dp_i$ 为修改 1~i 使 $a$ 严格单调上升的最小代价。有 $cost_{j,i}$ 为把区间 $[j,i]$ 严格单调上升的最小代价，自然得到 dp 方程：
$$dp_i=\min \{ f_j+1=f_i dp_j+cost_{j,i}\}$$
$\ \ \ \ \ \ \ $因为有 $dp_j+1=dp_i$，可以有 $cost_{j,i}$ 的决策中，$\forall k → [j,k]$ 所有元素为 $a_j$ 并且 $[k+1,l]$ 的元素都为 $a_i$。
$\ \ \ \ \ \ \ $有了猜想，如何证明结论成立？
偷了张图，可以自己体会一下。
$\ \ \ \ \ \ \ $偷懒就不证明了吧。。。反正 luogu 上面证明多得是。
$\ \ \ \ \ \ \ $有了这些，实际上我们遇到这样的值就进行 dp。最坏复杂度 $O(n^3)$。但是因为我们的数据随机，所以怎么 dp 都不死。xd
$\ \ \ \ \ \ \ $代码如下。
```cpp
#include<cstdio>
#include<algorithm>
#include<queue>
#define inf 1008600110086001ll
using namespace std;
vector<long long> G[35005];
long long a[35005],n;
long long Abs(long long x){return x<0?-x:x;}
namespace Subtasks{
long long dp[35005],seq[35005],sum1[35005],sum2[35005],ddpp[35005];
void Subtask1()
{
a[++n]=inf;
long long len=1;
seq[1]=a[1],dp[1]=1;
for(long long i=2;i<=n;++i)
{
if(a[i]>=seq[len]) seq[++len]=a[i],dp[i]=len;
else
{
long long whe=upper_bound(seq+1,seq+1+len,a[i])-seq;
seq[whe]=a[i],dp[i]=whe;
}
}
printf("%lld\n",n-len);
}
void prepareForSubtask2()
{
for(long long i=0;i<=n;++i) G[dp[i]].emplace_back(i),ddpp[i]=inf;
ddpp[0]=0;
a[0]=-inf;
}
void Subtask2()
{
for(long long i=1;i<=n;++i)
{
for(unsigned long long j=0;j<G[dp[i]-1].size();++j)
{
long long to=G[dp[i]-1][j];
if(a[to]<=a[i])
{
sum1[to-1]=sum2[to-1]=0;
for(long long k=to;k<=i;++k) sum1[k]=Abs(a[k]-a[to])+sum1[k-1],sum2[k]=Abs(a[i]-a[k])+sum2[k-1];
for(long long k=to;k<=i;++k) ddpp[i]=min(ddpp[i],ddpp[to]+sum1[k]-sum1[to]+sum2[i]-sum2[k]);
}
}
}
printf("%lld\n",ddpp[n]);
}
}
int main(){
scanf("%lld",&n);
for(long long i=1;i<=n;++i) scanf("%lld",&a[i]),a[i]-=i;
Subtasks::Subtask1();
Subtasks::prepareForSubtask2();
Subtasks::Subtask2();
return 0;
}
```
## 7.「GZOI2017」取石子游戏（博弈论类 dp）
$\ \ \ \ \ \ \ $[luogu](https://www.luogu.com.cn/problem/P5675)
$\ \ \ \ \ \ \ $我们因为不知道第一堆石子到底是哪一堆，所以说我们直接枚举。
$\ \ \ \ \ \ \ $我们考虑让 Bob 后手赢这场游戏，所以说 Alice 在一开始或者第二回合变成必败状。做了nim游戏的板子的都知道必败状是 $a_1 \oplus a_2 \oplus ... \oplus a_n=0$（$\oplus$ 为异或符号），我们要让 Alice 面对必败状，我们只能让剩下的 $n-1$ 堆石子异或起来大于等于第一堆。因为如果小于的话，Alice 一定能找到一种方法取第一堆石子使得 $a_1 \oplus a_2 \oplus ... \oplus a_n=0$。
$\ \ \ \ \ \ \ $同时，我们发现 $a_i$ 极其之小，异或起来最多也不过 $2^8-1=255$，我们考虑把它作为dp数组的一维。
$\ \ \ \ \ \ \ $那么我们定义 $dp_{i,j}$ 为前 $i$ 堆除了枚举的第 $k$ 堆外异或起来的数为 $j$ 的方案，然后每次跑一边 dp，统计一遍答案即可。
$\ \ \ \ \ \ \ $时间复杂度 $O(n^2 \log a_i)$，其中 $\log a_i$ 最大为 $8$，近似于常数。
$\ \ \ \ \ \ \ $代码如下。
```cpp
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
#define MOD 1000000007ll
using namespace std;
long long n,a[205],dp[205][260],ans;
int main(){
scanf("%lld",&n);
dp[0][0]=1;
for(long long i=1;i<=n;++i) scanf("%lld",&a[i]);
for(long long i=1;i<=n;++i)
{
for(long long j=1;j<=n;++j)
{
for(long long k=0;k<=255;++k)
{
if(i==j) dp[j][k]=dp[j-1][k];//这里一定要跳过，去掉我们枚举的“第一堆”
else dp[j][k]=dp[j-1][k]+dp[j-1][k^a[j]],dp[j][k]%=MOD;
}
}
for(long long j=a[i];j<=255;++j) ans+=dp[n][j],ans%=MOD;//统计第i堆作为第1堆的答案
}
printf("%lld",ans);
return 0;
}
```
## 8.「SCOI2005」最大子矩阵（简单 dp）
$\ \ \ \ \ \ \ $[luogu](https://www.luogu.com.cn/problem/P2331)
$\ \ \ \ \ \ \ $初看题目，$m \leq 2$。很容易发现我们经常做这种开两个算法去做的题。于是分析题目，觉得应该是可以的。
$\ \ \ \ \ \ \ $对于这种题，我们发现 $m = 1$ 的时候，就是我们的的经典模型：在 $n$ 个数中选 $k$ 个不相连的子串。我们可以定义 $dp_{i,j,0/1}$ 为第 $i$ 个选到第 $j$ 个子序列，对于 $a_i$ 选与不选两种情况。得到 dp 式：
$$\begin{cases}
dp_{i,j,1}=\max \{ dp_{i-1,j,1}+a_i,dp_{i-1,j-1,0}+a_i \}\\ dp_{i,j,0}=\max \{ dp_{i-1,j,1},dp_{i-1,j,0} \}\\
\end{cases}$$
$\ \ \ \ \ \ \ $答案即为 $\max \{dp_{n,k,0},dp_{n,k,1}\}$。
$\ \ \ \ \ \ \ $有了我们在 $m=1$ 的成功经验，为什么不去试试 $m=2$ 呢。
$\ \ \ \ \ \ \ $可见 $m=2$ 时只有 5 种情况。分别是：
- 空出一行；
- 选择左边而空出右边；
- 选择右边而空出左边；
- 左边和右边分别属于两个矩阵；
- 左右属于一个矩阵。
$\ \ \ \ \ \ \ $然后根据这些东西，我们一样可以像上面一样得到转移方程，可惜这里太小写不下。（XD其实是太长了）
$\ \ \ \ \ \ \ $看看代码就行了。
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m,k;
namespace std
{
namespace Subtask1
{
int dp[105][15][2];
int Solve()
{
for(int i=1;i<=n;++i)
{
int x;
scanf("%d",&x);
for(int j=1;j<=k;++j)
{
dp[i][j][1]=max(dp[i-1][j][1]+x,dp[i-1][j-1][0]+x);
dp[i][j][0]=max(dp[i-1][j][1],dp[i-1][j][0]);
}
}
return 0&printf("%d",max(dp[n][k][1],dp[n][k][0]));
}
}
namespace Subtask2
{
int dp[105][15][5];
int Solve()
{
memset(dp,-0x3f,sizeof dp);
for(int i=0;i<=n;++i) for(int j=0;j<=k;++j) dp[i][j][0]=0;
for(int i=1;i<=n;++i)
{
int a,b;
scanf("%d %d",&a,&b);
for(int j=1;j<=k;++j) dp[i][j][0]=max({dp[i-1][j][0],dp[i-1][j][1],dp[i-1][j][2],dp[i][j-1][3],dp[i-1][j][4]}),dp[i][j][1]=max({dp[i-1][j-1][0],dp[i-1][j][1],dp[i-1][j-1][2],dp[i-1][j][3],dp[i-1][j-1][4]})+a,dp[i][j][2]=max({dp[i-1][j-1][0],dp[i-1][j-1][1],dp[i-1][j][2],dp[i-1][j][3],dp[i-1][j-1][4]})+b,dp[i][j][3]=max({dp[i-1][j-1][1],dp[i-1][j-1][2],dp[i-1][j][3],(j>=2?dp[i-1][j-2][4]:-2147483647)})+a+b,dp[i][j][4]=max({dp[i-1][j-1][0],dp[i-1][j-1][1],dp[i-1][j-1][2],dp[i-1][j-1][3],dp[i-1][j][4]})+a+b;
}
return 0&printf("%d",max({dp[n][k][0],dp[n][k][1],dp[n][k][2],dp[n][k][3],dp[n][k][4]}));
}
}
}
using namespace std;
int main(){
scanf("%d %d %d",&n,&m,&k);
return m==1?Subtask1::Solve():Subtask2::Solve();
}
```
## 9.「SNOI2017」英雄联盟（背包 dp）
$\ \ \ \ \ \ \ $[luogu](https://www.luogu.com.cn/problem/P5365)
$\ \ \ \ \ \ \ $首先说一下哈，这个里面的 $n \leq 10^6$，没这么麻烦。
$\ \ \ \ \ \ \ $做 dp 题都需要简化题意，这道题的意思大概就是展示策略达到 $m$ 种的最小花费。
$\ \ \ \ \ \ \ $我们有 $n$ 个英雄，每个英雄都是有一个皮肤的数量 $k_i$ 和花费 $c_i$ 的。很容易联想到我们的背包。这道题就是把每一个英雄看成一个分组，每组都有一个数量，花费固定。很经典的分组背包问题。我们定义 $dp_{i,j}$ 为买掉 $i$ 个皮肤用掉 $j$ Q 币的最大方案数。有 dp 方程：
$$dp_{i,j}=\max \{ dp_{i-1,j-p \times c_i} \times p \}$$
$\ \ \ \ \ \ \ $其中 $1 \leq p \leq k_i$。注意初始化 $dp_0=1$，因为什么都不买也算作一种方案。
$\ \ \ \ \ \ \ $可以发现我们的二维数组死掉了。考虑优化空间。
$\ \ \ \ \ \ \ $我们看到只需要考虑前 $i-1$ 维，可以考虑滚掉。也可以看到后面一维，实际上这就是一个类似于 01 背包的优化方法。直接暴力滚掉二维，倒序枚举当前的 Q 币数，然后正常背包。dp 式改进为：
$$dp_j=\max \{ dp_{j - p \times c_i} \times p \}$$
$\ \ \ \ \ \ \ $然后枚举花费 Q 币数，如果有 $m \leq dp_q$，输出 $q$。
```cpp
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
long long n,m,dp[1000005],k[1000005],c[1000005],rest;
int main(){
scanf("%lld %lld",&n,&m);
for(long long i=1;i<=n;++i) scanf("%lld",&k[i]);
for(long long i=1;i<=n;++i) scanf("%lld",&c[i]),rest+=k[i]*c[i];
dp[0]=1;
for(long long i=1;i<=n;++i) for(long long j=rest;~j;--j) for(long long l=1;l<=k[i] && l*c[i]<=j;++l) dp[j]=max(dp[j],dp[j-l*c[i]]*l);
for(long long i=0;i<=rest;++i) if(dp[i]>=m) return printf("%lld",i)&0;
return 0;
}
```
## 10.「HAOI2015」树上染色（树形类背包 dp）
$\ \ \ \ \ \ \ $[luogu](https://www.luogu.com.cn/problem/P3177)
$\ \ \ \ \ \ \ $大概意思就是说，我们要在 $n$ 个节点中把 $k$ 个涂黑，然后计算两两黑节点和白节点的距离之和，求这个最大值？
$\ \ \ \ \ \ \ $做过树形 dp 的人很容易想到 定义 $dp_{i,j}$ 为第 $i$ 个节点，并以 $i$ 为根在子树上选择 $j$ 个黑色节点的最大贡献。如果您是这么定义的，那么肯定 gg 了。
$\ \ \ \ \ \ \ $为什么呢？因为我们不只有这颗子树，在这棵子树外，有更多的节点。
$\ \ \ \ \ \ \ $所以说我们只能根据套路，发现我们定义 $dp_{i,j}$ 为以 $i$ 为根的子树选择 $j$ 个黑色节点的贡献。但是计算贡献是极慢的。所以说我们要考虑如何计算。
$\ \ \ \ \ \ \ $考虑我们只有 $k$ 个黑色节点。在这里用了 $l$ 个，那么外面不就是 $k-l$ 个了么？
$\ \ \ \ \ \ \ $所以说，我们在统计的时候，不以点去储存，而是用边去计算贡献。对于我们的 $dp$ 数组，贡献有：
$$dp_{to,l}+l*(k-l)*val+(size_{to}-l)*(n-k+l-size_{to})*val$$
$\ \ \ \ \ \ \ $其中 $val$ 为当前边的权值，而 $size_i$ 为以 $i$ 为根的子树的大小。枚举 $l$。
$\ \ \ \ \ \ \ $这实际上就变成了一个背包问题。考虑每一棵子树分配多少黑色节点，大概就是分配体积，算出贡献。
```cpp
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define mp make_pair
#define Edge pair<long long,long long>
using namespace std;
vector<Edge> G[2005];
long long dp[2005][2005],size[2005],n,k;
void DP(long long now,long long pre)
{
size[now]=1;
dp[now][0]=dp[now][1]=0;
for(unsigned long long i=0;i<G[now].size();++i)
{
long long to=G[now][i].first,val=G[now][i].second;
if(to==pre) continue;
DP(to,now);
size[now]+=size[to];
for(long long j=size[now];~j;--j) for(long long l=0;l<=min(j,size[to]);++l) if(dp[now][j-l]!=-1) dp[now][j]=max(dp[now][j],dp[now][j-l]+dp[to][l]+l*(k-l)*val+(size[to]-l)*(n-k+l-size[to])*val);
}
}
int main(){
memset(dp,-1,sizeof dp);
scanf("%lld %lld",&n,&k);
for(long long i=1;i<n;++i)
{
long long u,v,val;
scanf("%lld %lld %lld",&u,&v,&val);
G[u].push_back(mp(v,val));
G[v].push_back(mp(u,val));
}
DP(1,0);
printf("%lld",dp[1][k]);
return 0;
}
```