DP专题

背包 DP

P1049 [NOIP2001 普及组] 装箱问题

本质上 $0$-$1$ 背包的变形。用滚动数组优化，令 $f_i$ 为前 $i$ 个物品最大的价值（即重量最大），输出 $V - f_V$ 即可。

P1048 [NOIP2005 普及组] 采药

赤裸裸的 $ 0$-$1 $ 背包，直接套板子就好了。

P1060 [NOIP2006 普及组] 开心的金明

还是 $0$-$1$ 背包，只不过要把重要值乘上价格，用滚动数组优化就好了。

P1734 最大约数和

筛法筛出 $1$ 到 $S$ 间所有整数的约数之和，那么就是 $0$-$1$背包问题，数字大小为重量，约数的和为价值，直接求最大值即可。

P1507 NASA的食物计划

$0$-$1$背包的变种，在重量之上再添加一个质量，循环变为三层。

P2722 [USACO3.1]总分 Score Inflation

重点注意每一类题目可以重复选择，那么就是完全背包问题，只不过把重量和分数换了个名字叫做时间和分数罢了。

P1832 A+B Problem（再升级）

筛出质数，那么这道题就是完全背包的变形，每一次将上一次得到的答案加上，注意设置边界 $f_0 = 1$。

P1164 小A点菜

看上去和上一道一样，都是统计类型的题，但是这道题的菜的价格可能一样，所以就是用 $0$-$1$ 背包的思路。

P1833 樱花

混合背包。思路就是把这几种背包全部转化为 $0$-$1$背包，但这样内存就不允许了（存在完全背包），所以我们需要采用二进制拆分的方法，把这些物品合并起来，避免了不必要的决策。

区间DP & 环形DP

P1880 [NOI1995] 石子合并

区间 $\texttt{DP}$ 中最经典最基础的题。每次按照区间从小到大枚举每个区间，再枚举区间内的中间点，更新答案。

P1063 [NOIP2006 提高组] 能量项链

和上一题相似，也是求最大值的问题。

P3146 [USACO16OPEN]248 G

跟石子合并几乎一样，只不过在更新时要判断端点是否一致，更新所增加的值并不是区间和了，而是 $1$。

P4342 [IOI1998]Polygon

基本上和石子合并一样，只不过石子之间相加变成了加法或者乘法，出现了乘法就应该谨慎起来，边权可能为负数，那么就会有负负得正的情况，就需要分类讨论，细节有一点点复杂，可以去看我的题解。

P4170 [CQOI2007]涂色

套路一致。只不过需要分类讨论，如果该区间左右端点颜色相同，那么答案就是 $\max(f_{l+1,r},f_{l,r-1})$，否则就枚举中心点由上一个区间更新答案。

CF607B Zuma

这道题和涂色很相似，但与这些题目不同的是，设置边界时不仅要设置 $f_{i,i}$ 的，还应该设置一个特殊的边界， $f_{i,i-1}$，可能会有很多疑点，这是为了判断长度为 $2$ 的回文串的情况

练习题

摘录了一些挺有趣的 $\texttt{DP}$ 题。

Atcoder DP 26题

Educational DP Contest

AT4522 Frog 1

令 $f_i$ 为第 $1$ 块石头跳到第 $i$ 块石头的最小费用，不难列出以下的状态转移方程：

\[f_i = \max(f_{i-1}+abs(h_i - h_{i-1}),f_{i-2} +abs(h_i-h_{i-2}))\]

边界条件为 $f_1 = 0$，答案就是 $f_n$。

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

int n,h[100010],f[100010];
main(){
	cin >> n;
	for (int i = 1;i <= n;i++) cin >> h[i];
	f[1] = 0,f[2] = abs(h[1] - h[2]);
	for (int i = 3;i <= n;i++){
		f[i] = min(f[i-1] + abs(h[i-1] - h[i]),f[i-2] + abs(h[i-2] - h[i]));
	}
	cout << f[n];
	return 0;
}

AT4523 Frog 2

和上一题大同小异，只要把转移部分改为当前石头前 $k$ 个的价值最大即可。

AT4524 Vacation

令 $f_{i,j}$ 为第 $i$ 天做第 $j$ 种活动的幸福值的最大值，那么答案就呼之欲出了。

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

int n,f[100010][4];
struct Day{
	int a,b,c;
}d[100010];
main(){
	cin >> n;
	for (int i = 1;i <= n;i++) cin >> d[i].a >> d[i].b >> d[i].c;
	d[0].a = d[0].b = d[0].c = 0;
	for (int i = 1;i <= n;i++){
		{// swim
			f[i][1] = max(f[i-1][2],f[i-1][3]) + d[i].a;
		}
		{// catch
			f[i][2] = max(f[i-1][1],f[i-1][3]) + d[i].b;
		}
		{// homework
			f[i][3] = max(f[i-1][1],f[i-1][2]) + d[i].c;
		}
	}
	cout << max(max(f[n][1],f[n][2]),f[n][3]);
}

AT4525 Knapsack 1

$0$-$1$背包问题，没啥好说的了。

AT4526 Knapsack 2

$W$ 的值变大了，但 $v_i$ 的值缩小了，那么就考虑换一种滚动数组的方式来优化，将重量换为价值，$f_i$ 表示价值综合为 $i$ 的物品重量的最小值，那么在输出过程中从大到小枚举 $f_i$，当 $f_i \le W$ 时输出 $i$ 就可以了。

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

int n,W,w[110],v[110],f[1000010],maxn;
main(){
	memset(f,0x3f,sizeof(f));
	cin >> n >> W;maxn = n * 1000;
	for (int i = 1;i <= n;i++) cin >> w[i] >> v[i];
	f[0] = 0;
	for (int i = 1;i <= n;i++){
		for (int j = maxn;j >= v[i];j--){
			f[j] = min(f[j],f[j - v[i]] + w[i]);
		}
	}
	for (int i = maxn;i;i--){
		if (f[i] <= W) return cout << i,0;
	}
}

AT4528 Longest Path

也没什么好说的，几乎就是 $\texttt{DFS}$ 的板子。

#include <bits/stdc++.h>
#define pb push_back
using namespace std;

int n,m,ans,f[100010];
vector<int> g[100010];
bool v[100010];
void dfs(int x){
	if (v[x]) return;
	v[x] = 1;
	for (auto y:g[x]){
		dfs(y);
		f[x] = max(f[x],f[y] + 1);
	}
	ans = max(ans,f[x]);
}
main(){
	cin >> n >> m;
	for (int i = 1,x,y;i <= m;cin >> x >> y,g[x].pb(y),i++);
	for (int i = 1;i <= n;i++) dfs(i);
	cout << ans;
}

AT4529 Grid 1

这题和那个过河卒挺像的，在这道题中，一次只能够向下或者向右走一格。若当前格子合法，那么在状态转移的过程中只需从上面和左边的方案数相加取模即可。

注意边界设置！

#include <bits/stdc++.h>
#define mod 1000000007
using namespace std;

int n,m,f[1010][1010];
char a[1010][1010];
main(){
	cin >> n >> m;
	for (int i = 1;i <= n;i++) scanf("%s",a[i] + 1);
	f[0][1] = 1;
	for (int i = 1;i <= n;i++){
		for (int j = 1;j <= m;j++){
			if (a[i][j] == '.')
				f[i][j] = (f[i-1][j] + f[i][j-1]) % mod;
		}
	}
	cout << f[n][m];
}

杂题

[ABC266D] Snuke Panic (1D)

瞟了一眼题解，发现挺简单的……

这题的时间 $T$ 最大只到 $10^5$，考虑根据时间去转移。定义 $f_{i,j}$ 为第 $i$ 个时间点在第 $j$ 个洞时的最大价值，由于 $1$ 个时间点内只能移动 $1$ 步，不难得到转移方程：

\[f_{i,j} = \max(f_{i-1,j-1},f_{i-1,j},f_{i-1,j+1})+a_{i,j}\]

CF2B The least round way

只能向右和向下，显然是 DP 。

根据小学数学，积出现一个 $0$ 代表它的约数中必定出现一对 $2$ 和 $5$ ，因此我们求出每个格子内的数的因数 $2$ 和 $5$ 的个数。

令 $f_{i,j,0}$ 为从 $(0,0)$ 走到 $(i,j)$ 沿途乘积值的约数 $2$ 的数量，$f_{i,j,1}$ 为从 $(0,0)$ 走到 $(i,j)$ 沿途乘积值的约数 $5$ 的数量。

易得：

\[f_{i,j,0} = \min(f_{i-1,j,0},f_{i,j-1,0}) + a_{i,j,0}\]

\[f_{i,j,1} = \min(f_{i-1,j,1},f_{i,j-1,1}) + a_{i,j,1}\]

处理边界第一行和第一列即可。

注意要特判！！！

任何数乘 $0$ 都得 $0$，所以如果我们最终答案大于 $0$ ，我们就选择包含 $0$ 的那个数的路径就好了。

对于输出路径就不赘述了。代码。

lywqwq

DP

DP专题

背包 DP

区间DP & 环形DP

练习题

Atcoder DP 26题

杂题