算法模板（4）：动态规划（1）

动态规划

• 闫氏 $dp$ 分析法：

1. 集合：怎么划分。通常以集合的划分来定义数组。$f(i,j)$：选前 $i$ 个物品.

• 体积不超过 $j$。全部初始化为 $0$；$j$ 非负时状态才合法。
• 体积恰好是 $j$。$f(0,0)$初始化为 $0$，其他的初始化为负无穷。$j$ 非负时状态才合法。
• 体积不小于 $j$。$f(0,0)$初始化为 $0$，其他状态初始化为正无穷。$j$ 小于 $0$ 时状态依然合法。

2. 属性：通常只有三个，最大 / 最小 / 方案数。
3. 状态计算：常用的方法是看看第 $i$ 个物品选还是不选。

1.背包问题

（1）01背包

模板

注意，状态转移方程应该是 $f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i])$，但是由于前面写了个$f[i][j]=f[i-1][j]$，因此就成了代码中的那个样子。

//v是物体的体积，w是物体的价值
int v[maxn], w[maxn], f[maxn][maxn];
int N, V;
int main() {
	scanf("%d%d", &N, &V);
	for (int i = 1; i <= N; i++) scanf("%d%d", &v[i], &w[i]);
	for (int i = 1; i <= N; i++) {
		for (int j = 0; j <= V; j++) {
			f[i][j] = f[i - 1][j];
			if (j >= v[i]) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
		}
	}
	printf("%d\n", f[N][V]);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

那么，这个怎么改成一维呢？我们发现，在计算$f[i][j]$的时候，用到的之后上面那一层$f[i-1][j]和f[i-1][j-v[i]],v[i]<=j$，因此可以这么改：

for (int i = 1; i <= N; i++) {
    for (int j = V; j >= v[i]; j--) {
        f[j] = max(f[j], f[j - v[i]] + w[i]);
    }
}
printf("%d\n", f[V]);
1
2
3
4
5
6

12. 背包问题求具体方案

• 01背包求方案
• 这里跑一边dp。如果要满足字典序最小的话，可以用贪心法。从1~N的物品，可选可不选的情况下要选上。
• 第一遍跑dp要从N到1，这样子最终的答案保存在了$f(1,V)$里面，然后第二次输出方案的时候就可以从1~N输出了。第一遍从1到N跑dp的话，还真是不好设计。

#include
#include
using namespace std;
const int maxn = 1010;
int f[maxn][maxn], v[maxn], w[maxn], N, V;
int main() {
	scanf("%d%d", &N, &V);
	for (int i = 1; i <= N; i++) scanf("%d%d", &v[i], &w[i]);
	for (int i = N; i >= 1; i--) {
	    //注意这里从小到大循环并不是完全背包。因为这个是二维数组，不是一维数组。
		for (int j = 0; j <= V; j++) {
			f[i][j] = f[i + 1][j];
			if (j >= v[i]) f[i][j] = max(f[i][j], f[i + 1][j - v[i]] + w[i]);
		}
	}
	int j = V;
	for (int i = 1; i <= N; i++) {
		if (j >= v[i] && f[i + 1][j - v[i]] + w[i] == f[i][j]) {
			printf("%d ", i);
			j -= v[i];
		}
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

（2）完全背包

朴素写法：

for (int i = 1; i <= N; i++) {
    for (int j = 0; j <= V; j++) {
        for (int k = 0; k * v[i] <= j; k++) {
            f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
        }
    }
}
printf("%d\n", f[N][V]);
1
2
3
4
5
6
7
8

改进一下：

for (int i = 1; i <= N; i++) {
	for (int j = 0; j <= V; j++) {
		f[i][j] = f[i - 1][j];
		if (j >= v[i]) f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
	}
}
1
2
3
4
5
6

改为1维滚动数组

for (int i = 1; i <= N; i++) {
	for (int j = v[i]; j <= V; j++){
		f[j] = max(f[j], f[j - v[i]] + w[i]);
	}
}
1
2
3
4
5

（3）多重背包

6. 多重背包问题 III - AcWing题库

题意：第 $i$ 种物品最多有 $s_i$ 件，每件体积是 $v_i$，价值是 $w_i$。

法一：朴素写法 $O(n\ast v\ast s)$：

for (int i = 1; i <= N; i++) {
	for (int j = 0; j <= V; j++) {
		for (int k = 0; k <= s[i] && k * v[i] <= j; k++) {
			f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
		}
	}
}
1
2
3
4
5
6
7

法二：二进制拼凑 $O(n\ast V\ast logV)$

改进写法：
打包。我们用一组 $2$ 的 $k-1$ 次幂的数字，可以凑出 $1\sim 2^{k-1}$ 的任何一个数字。那么我们可以用这么一个性质，将这些物品打包。而凑数字的过程又和 $01$ 背包的选的过程是一模一样的。因此就转化成了 $01$ 背包问题。
注意这次要用滚动数组，不然会爆内存。那个数组的大小要开到大于 $v\ast logS$.

#include
#include
using namespace std;
const int maxn = 25000, maxm = 2010;
int v[maxn], w[maxn], f[maxm];
int N, V;
int main() {
	scanf("%d%d", &N, &V);
	int cnt = 0;
	for (int i = 1; i <= N; i++) {
		int a, b, s;
		scanf("%d%d%d", &a, &b, &s);
		int k = 1;
		while (k <= s) {
			cnt++;
			v[cnt] = a * k;
			w[cnt] = b * k;
			s -= k;
			k *= 2;
		}
		if (s > 0) {
			cnt++;
			v[cnt] = a * s;
			w[cnt] = b * s;
		}
	}

	N = cnt;
	for (int i = 1; i <= N; i++) {
		for (int j = V; j >= v[i]; j--) {
			f[j] = max(f[j], f[j - v[i]] + w[i]);
		}
	}
	printf("%d\n", f[V]);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

法三：滑动窗口 $O(n\ast V)$

• 我们需要保留上一层的值和本层的值。每次把最后一个元素扔掉，把第一个元素加进来，单调队列保存的是体积（即下标），因此单调队列维护的是 $f(i-1,\ast )$ 相对大小（单调递减）。因此每次更新的时候，需要判断队尾元素和新加进来的相对大小即可，即 $\frac{k-q[tt]}{v}\ast w+g[q[tt]]\le q[k]$ . 其中 $f$ 是当前层的数据，$q$ 表示上一层的数据.

#include
using namespace std;
const int N = 1010, M = 200010;
int f[M], g[M], q[M];
int n, m;
int main()
{
    scanf("%d%d", &n, &m);
    
    for(int i = 1; i <= n; i++)
    {
        int v, w, s;
        scanf("%d%d%d", &v, &w, &s);
        //g存的是上一层的f的值
        memcpy(g, f, sizeof f);
        for(int j = 0; j < v; j++)
        {
            
            int hh = 0, tt = -1;
            for(int k = j; k <= m; k += v)
            {
                //判断队头元素是否已经滑出窗口
                if(hh <= tt && k - q[hh] > s * v) hh++;
                //借助滑动窗口最大值更新答案
                if(hh <= tt) f[k] = max(g[k], g[q[hh]] + (k - q[hh]) / v * w);
                //单调队列删除冗余元素
                while(hh <= tt && (k - q[tt]) / v * w + g[q[tt]] <= g[k]) tt--; 
                q[++tt] = k;
            }
        }
    }
    printf("%d\n", f[m]);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

（4）分组背包问题

模板题

• 题意：有 $N$ 组物品和一个容量是 $V$ 的背包. 每组物品有若干个，同一组内的物品最多只能选一个. 每件物品的体积是 $v_{ij}$，价值是 $w_{ij}$，其中 $i$ 是组号，$j$ 是组内编号.

#include
#include
using namespace std;
const int maxn = 110, maxv = 110;
int v[maxn][maxn], w[maxn][maxn], f[maxv], s[maxn];
int N, V;
int main() {
	scanf("%d%d", &N, &V);
	for (int i = 1; i <= N; i++) {
		scanf("%d", &s[i]);
		for (int j = 0; j < s[i]; j++) {
			scanf("%d%d", &v[i][j], &w[i][j]);
		}
	}
//其实这个和01背包的思路差不多，但是一定不要把第二重和第三重循环反过来。如果反过来的话，不能保证每组只选一个物品。
	for (int i = 1; i <= N; i++) {
		for (int j = V; j >= 0; j--) {
			for (int k = 0; k < s[i]; k++) {
				if (j >= v[i][k]) f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
			}
		}
	}
	printf("%d\n", f[V]);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

（5）二维费用背包

1022. 宠物小精灵之收服

• 二维费用背包问题。
• 就是说有 $n$ 个物品，手里有两种容量 $V_1,V_2$，每选择一个物品，占据的第一种容量为 $v_1$，占据第二种容量为 $v_2$.
• 体积是二维的。也就是说皮卡丘抓小精灵，小精灵既会造成伤害又会消耗精灵球。问最多能抓多少只小精灵，而抓的小精灵数量相同的时候，最少消耗多少 $HP$？
• $f(i,j,k)$：表示从前 $i$ 个物品中挑选，费用 $1$ 花费不超过 $j$，费用 $2$ 花费不超过 $k$，物品价值的最大值。
• 对于这道题，压缩到二维之后，由于皮卡丘的 $HP$ 不可以为 $0$，因此答案是 $f(V1,V2-1)$.

#include
#include
using namespace std;
const int maxn = 1010, maxm = 510, maxk = 110;
int v1[maxk], v2[maxk], f[maxn][maxm], V1, V2, N;
int main() {
	scanf("%d%d%d", &V1, &V2, &N);
	for (int i = 1; i <= N; i++) scanf("%d%d", &v1[i], &v2[i]);
	for (int i = 1; i <= N; i++) {
		for (int j = V1; j >= v1[i]; j--) {
			for (int k = V2; k >= v2[i]; k--) {
				f[j][k] = max(f[j][k], f[j - v1[i]][k - v2[i]] + 1);
			}
		}
	}
	int ans1 = f[V1][V2 - 1], ans2 = V2;
	for (int j = 0; j <= V2 - 1; j++) {
		if (f[V1][j] == ans1) {
			ans2 = j; break;
		}
	}
	printf("%d %d\n", ans1, V2 - ans2);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

1020. 潜水员

• 二维费用求最小值.
• 体积：一共有 $k$ 种 物品，对于第 $i$ 种物品，第一维费用是 $v_{1i}$，第二维费用是 $v_{2i}$，价值 是 $w_i$，每个物品至多被选一次。求一个选择方案，使得第一维费用不少于 $n$，第二维费用不少于 $m$ 且 总价值最小
• 这道题有所改变，$f(i,j,k)$表示选前 $i$ 个物品，费用 $1$ 不少于 $j$，费用 $2$ 不少于 $k$.
• 由于 $j$ 和 $k$ 是负数时，$f(i,j,k)=0$，因此这个状态和 $0$ 等效，那么此时 $f(i,j,k)=f(i,0,0)$.
• $f(0,0,0)=0$, $f(0,j,k)=INF$ 或 $-1$，因为不可以从 $f(0,j,k)$ 转移过来，算作不可达状态。因为我们如果保证恰好是凑出 $(j,k)$ 的话，那么只能从 $(0,0)$ 的状态转移过来。

#include
#include
#include
using namespace std;
const int maxn = 25, maxm = 85;
int V1, V2, N, f[maxn][maxm];
int main() {
	memset(f, 0x3f, sizeof f);
	f[0][0] = 0;
	scanf("%d%d%d", &V1, &V2, &N);
	for (int i = 0; i < N; i++) {
		int v1, v2, w;
		scanf("%d%d%d", &v1, &v2, &w);
		for (int j = V1; j >= 0; j--) {
			for (int k = V2; k >= 0; k--) {
				f[j][k] = min(f[j][k], f[max(0, j - v1)][max(0, k - v2)] + w);
			}
		}
	}
	printf("%d\n", f[V1][V2]);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

（6）混合背包问题

模板题

• 混合背包就是物品有的只能选 $1$ 件，有的可以选 $s$ 件，有的可以选无穷多件。
• 只有第二重循环不一样。所以边读入数据边求就可以。
• 注意到 $01$ 背包问题就是多重背包问题的特殊情况，可以统一处理。

#include
#include
using namespace std;
const int maxv = 1010;
int f[maxv], N, V;
int main() {
	scanf("%d%d", &N, &V);
	for (int i = 1; i <= N; i++) {
		int v, w, s;
		scanf("%d%d%d", &v, &w, &s);
		if (s == 0) {
			for (int j = v; j <= V; j++) f[j] = max(f[j], f[j - v] + w);
		}
		else {
			if (s == -1) s = 1;
			for (int k = 1; k <= s; s -= k, k *= 2) {
				for (int j = V; j >= v * k; j--) f[j] = max(f[j], f[j - k * v] + k * w);
			}
			if (s > 0) {
				for (int j = V; j >= v * s; j--) f[j] = max(f[j], f[j - s * v] + s * w);
			}
		}
	}
	printf("%d\n", f[V]);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

（7）有依赖的背包问题

10. 有依赖的背包问题

• 题意：有 $N$ 个物品和一个容量是 $V$ 的背包。物品之间具有依赖关系，且依赖关系组成一棵树的形状。如果选择一个物品，则必须选择它的父节点。求背包物品最大价值。
• $f(u,j)$：从 $u$ 为根的子树中选，且总体积不超过 $j$ 时的价值最大值。
• 复杂度：$O(n^3)$
• 补充思路：对于结点 $u$，$son$ 是 $u$ 的一个子结点，$f(son,k),k\in [0,m-v[u]]$ 作为一组物品，分组背包.

#include
using namespace std;
const int N = 110, V = 110;

int f[N][V], v[N], w[N];
int h[N], e[N], ne[N], idx;
int n, m;

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void dfs(int u)
{
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int son = e[i];
        dfs(son);
        //分组背包，第一层循环背包体积，第二层循环每组的物品，即子树占用的体积。
        for(int j = m - v[u]; j >= 0; j--)
        {
            for(int k = j; k >= 0; k--)
            {
                f[u][j] = max(f[u][j], f[u][j - k] + f[son][k]);
            }
        }
    }
    //把根节点放进去
    //注意，这里不能取max，因为这个模拟的是选子节点必须选父结点的过程。
	//如果取max的话就意味着有些方案取子结点但没取父结点，结果可能会偏大。
    for(int j = m; j >= v[u]; j--)
    {
        f[u][j] = f[u][j - v[u]] + w[u];
    }
    //放不进根节点的方案，全部置为0.
    for(int j = 0; j < v[u]; j++) f[u][j] = 0;
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    int root;
    for(int i = 1; i <= n; i++)
    {
        int p;
        scanf("%d%d%d", &v[i], &w[i], &p);
        if(p == -1) root = i;
        else add(p, i);
    }
    dfs(root);
    printf("%d\n", f[root][m]);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

优化至 $O(n^2)$

//林靖轩的写法
int dfs(int u)
{
    f[u][v[u]] = w[u], f[u][0] = 0;
    sz[u] = v[u];
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int son = e[i];
        sz[u] += dfs(son);
        //分组背包，第一层循环背包体积，第二层循环每组的物品，即子树占用的体积。
        for(int j = min(sz[u], m); j >= v[u]; j--)
        {
            for(int k = j - v[u]; k >= 0; k--)
            {
                f[u][j] = max(f[u][j], f[u][j - k] + f[son][k]);
            }
        }
    }
    //放不进根节点的方案，全部置为0.
    for(int j = 0; j < v[u]; j++) f[u][j] = 0;
    return sz[u];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

2.计数类DP

• 计数类 $dp$ 通常的套路是$f(0,0)=1$，定义的状态也是恰好凑成 j. 然后看第 $i$ 个数字选还是不选.

01背包计数

278. 数字组合

• 给定N个正整数$A_1,A_2,\dots ,A_N$，从中选出若干个数，使它们的和为 $M$，求有多少种选择方案.
• 都是这个套路，f(0, 0) 初始化为1.
• $f(0,0)=1,f(i,j)=f(i-1,j)+f(i,j-A_i)$.
• 方案数一定小心会不会爆 $int$ .

#include
#include
using namespace std;
const int maxm = 10010;
int N, M, f[maxm];
int main() {
	scanf("%d%d", &N, &M);
	f[0] = 1;
	for (int i = 0; i < N; i++) {
		int a;
		scanf("%d", &a);
		for (int j = M; j >= a; j--) {
			f[j] += f[j - a];
		}
	}
	printf("%d\n", f[M]);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

11. 背包问题求方案数

• 题意：有 $N$ 件物品和一个容量是 $V$ 的背包。每件物品只能使用一次。第 $i$ 件物品的体积是 $v_i$，价值是 $w_i$。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出 最优选法的方案数。注意答案可能很大，请输出答案模 $10^9+7$ 的结果。
• 注意这个题和上个题的区别，一个是恰好凑成 $m$，一个是凑成不超过 $m$.
• $f(i,j)$：前 $i$ 个物品，凑出体积恰好为 $j$ 的方案数（若定义成不超过 $j$，大雪菜说不好写，还要用到容斥原理）。
• 如果把此 $dp$ 问题看作一个 $DAG$ 上的最长路径统计问题，那么图的终点一定在最后一排即 $f[n,j]$. 因此方案数要把最后一排全部统计上。

二维：

#include
using namespace std;
const int N = 1010, mod = 1e9 + 7;

int f[N][N], v[N], w[N], cnt[N][N];
int n, m;
int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d%d", &v[i], &w[i]);
    }
    for(int i = 0; i <= n; i++) cnt[i][0] = 1;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 0; j <= m; j++)
        {
            f[i][j] = f[i - 1][j], cnt[i][j] = cnt[i - 1][j];
            if(j >= v[i])
            {
                if(f[i][j] == f[i - 1][j - v[i]] + w[i])
                {
                    cnt[i][j] = (cnt[i][j] + cnt[i - 1][j - v[i]]) % mod;
                }
                else if(f[i][j] < f[i - 1][j - v[i]] + w[i])
                {
                    cnt[i][j] = cnt[i - 1][j - v[i]];
                    f[i][j] = f[i - 1][j - v[i]] + w[i];
                }
            }
        }
    }
    int res = 0;
    for(int j = 0; j <= m; j++)
    {
        if(f[n][j] == f[n][m]) res = (res + cnt[n][j]) % mod;
    }
    printf("%d\n", res);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

压到1维滚动数组：

#include
#include
#include
using namespace std;
const int maxn = 1010, mod = 1000000007;
int N, V, f[maxn], g[maxn];
int main() {
	scanf("%d%d", &N, &V);
	memset(f, -0x3f, sizeof f);
	f[0] = 0, g[0] = 1;
	for (int i = 1; i <= N; i++) {
		int v, w;
		scanf("%d%d", &v, &w);
		for (int j = V; j >= v; j--) {
			int maxv = max(f[j], f[j - v] + w);
			int cnt = 0;
            //在决策是否选择第i个物品时，需要看maxv是从哪个值过去的。
			if (maxv == f[j]) cnt += g[j];
			if (maxv == f[j - v] + w) cnt += g[j - v];
			cnt %= mod;
			g[j] = cnt, f[j] = maxv;
		}
	}
	int res = 0, ans = 0;
	for (int i = 0; i <= V; i++) res = max(res, f[i]);
	for (int i = 0; i <= V; i++) {
		if (f[i] == res) ans = (ans + g[i]) % mod;
	}
	printf("%d\n", ans);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

完全背包计数

• 完全背包计数注意循环方向。

1023. 买书

• 小明手里有n元钱全部用来买书，书的价格为10元，20元，50元，100元。问小明有多少种买书方案？（每种书可购买多本）
• $f(0,0)=0.f(i,j)=f(i-1,j)+f(i-1,j-a_i)$.

#include
#include
using namespace std;
const int maxm = 1010;
int N, f[maxm], a[] = { 10, 20, 50, 100 };
int main() {
	scanf("%d", &N);
	f[0] = 1;
	for (int i = 0; i < 4; i++) {
		for (int j = a[i]; j <= N; j++) {
			f[j] += f[j - a[i]];
		}
	}
	printf("%d\n", f[N]);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

900. 整数划分

• 题意：一个正整数n可以表示成若干个正整数之和，形如：$n=n_1+n_2+\dots +n_k$，其中$n_1\ge n_2\ge \dots \ge n_k,k\ge 1$。我们将这样的一种表示称为正整数 $n$ 的一种划分。现在给定一个正整数n，请你求出 $n$ 共有多少种不同的划分方法。
• 这个题类似一个完全背包问题，物品的体积分别是 $1\sim n$，每个物品选的次数无限制，问选出的物品体积恰好为n的选法有多少种。

法一

• $f(i,j)$：在前 $i$ 个物品中选体积为 $j$ 的方案数。$f(0,0)=0.f(i,j)=f(i-1,j)+f(i,j-i)$.

• 压缩成一维：

#include
using namespace std;
const int maxn = 1010, mod = 1000000007;
int f[maxn], N;
int main() {
	scanf("%d", &N);
	f[0] = 1;
	for (int i = 1; i <= N; i++) {
		for (int j = i; j <= N; j++) {
			f[j] = (f[j] + f[j - i]) % mod;
		}
	}
	printf("%d\n", f[N]);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

法二

• $f(i,j)$：所有的总和是 $i$，并且恰好表示成 $j$ 个数的方案。对于 $f(i,j)$ 中的每一个方案，最小值是1时，为$f(i-1,j-1)$；最小值大于1，可以把每个数都减去1，即，$f(i-j,j)$. 因此，$f(0,0)=1.f(i,j)=f(i-1,j-1)+f(i-j,j)$.
• $ans=f(n,1)+f(n,2)+...+f(n,n)$.

#include
const int maxn = 1010, mod = 1000000007;
int f[maxn][maxn], N;
int main() {
	scanf("%d", &N);
	f[0][0] = 1;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= i; j++) {
			f[i][j] = (f[i - 1][j - 1] + f[i - j][j]) % mod;
		}
	}
	int ans = 0;
	for (int j = 1; j <= N; j++) ans = (ans + f[N][j]) % mod;
	printf("%d\n", ans);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

3.线性DP

（1）数字三角形

模板题

有一个易错点。因为这次是有负数的，所以要吧 $f$ 初始化为 $-INF$，这个和代码设计有关。
感觉数字三角形还是从下往上走比较简单。

void solve() {
	for (int i = 0; i <= N; i++) {
		for (int j = 0; j <= i + 1; j++) {
			f[i][j] = -INF;
		}
	}
	f[1][1] = a[1][1];
	for (int i = 2; i <= N; i++) {
		for (int j = 1; j <= i; j++) {
			f[i][j] = max(f[i - 1][j - 1] + a[i][j], f[i - 1][j] + a[i][j]);
		}
	}
	int ans = -INF;
	for (int j = 1; j <= N; j++) ans = max(ans, f[N][j]);
	printf("%d\n", ans);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

1027. 方格取数

• 题意：设有 $N\times N$ 的方格图，我们在其中的某些方格中填入正整数，而其它的方格中则放入数字 0. 某人从图中的左上角 A 出发，可以向下行走，也可以向右行走，直到到达右下角的 B 点。在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字 0）。此人从 A 点到 B 点共走了两次，试找出两条这样的路径，使得取得的数字和为最大。
• 这道题是不可以走两次，把路径记录下来的。因为两次都选择最优解的话，总体不一定是最优解。比如第一次可以不选择最优解，拿走一部分数字，第二次可以把剩下所有数字都拿走。但是，第一次选择最优解的话，可能第二次走的时候剩下的数字并不能拿走完。
• 这个题设 $f(k,i_1,i_2)$ 表示两条路径数字之和，两次位于点的位置分别为 $(i_1,j_1),(i_2,j_2)$，$k=i_1+i_2=j_1+j_2$，第一层先枚举 $k$，其实就是枚举走了多少步。然后一圈一圈向外扩展，因此每个格子只会走一次，不会重复。
• 两次走到同一点，等价于 $i_1+j_1=i_2+j_2$，且 $i_1=i_2$

#include
using namespace std;
const int maxn = 15;
int N, f[maxn * 2][maxn][maxn], w[maxn][maxn];
int main() {
	scanf("%d", &N);
	int x, y, c;
	while (scanf("%d%d%d", &x, &y, &c) && x) {
		w[x][y] = c;
	}
	for (int k = 2; k <= 2 * N; k++) {
		for (int i1 = 1; i1 <= N; i1++) {
			for (int i2 = 1; i2 <= N; i2++) {
				int j1 = k - i1, j2 = k - i2;
				if (j1 < 1 || j1 > N || j2 < 1 || j2 > N) continue;
				int& x = f[k][i1][i2];
				int t = w[i1][j1];
				if (i1 != i2) t += w[i2][j2];
				x = max(x, f[k - 1][i1 - 1][i2 - 1] + t);
				x = max(x, f[k - 1][i1 - 1][i2] + t);
				x = max(x, f[k - 1][i1][i2 - 1] + t);
				x = max(x, f[k - 1][i1][i2] + t);
			}
		}
	}
	printf("%d\n", f[2 * N][N][N]);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

275. 传纸条

• 题意：找到从 $(1,1)$ 到 $(m,n)$ 的两条路径，两条路径除了起点和终点外没有相交的点，且两条路径的点权之和最大。
• 这个题呀，和方格取数的做法一模一样。
• 证明：

1. 第二次传纸条改个方向，和从左上到右下传是等效的。
2. 任何两条路径，都可以改为一条路径在另一条路径的上方。比如这个，交换颜色就行。
   
3. 第三点，把实线换成虚线，结果不会变差。因为重合的点，第二次经过的时候是 0，但是绕个圈之后，对称点不一定是 0.
   

• 因此，这道题只需要改一下读入，以及注意N和M，其他的都一样。
• 当然，这道题完全可以加一句判断，除了起点和终点，只有 $i_1\ne i_2$ 时才更新状态，这样也是对的
• 因此，不管是在方格取数中，还是在本问题中，走的两条路径，除了起点和终点外，一定没有交点。

（2）最长上升子序列（LIS）

模板题

动态规划嘛，看看需要几维才能把状态表示出来。先考虑1维。一维不够再上升。其实几维不代表循环就有几重。
朴素版：

void solve() {
	for (int i = 1; i <= N; i++) {
		f[i] = 1;
		for (int j = 1; j <= i; j++) {
			if (a[j] < a[i]) f[i] = max(f[i], f[j] + 1);
		}
	}
	int ans = 0;
	//千万小心，答案是取max，不是f[N].
	for (int i = 1; i <= N; i++) ans = max(ans, f[i]);
	printf("%d\n", ans);
}
1
2
3
4
5
6
7
8
9
10
11
12

寻找公共子序列（倒着输出）：

void solve() {
	for (int i = 1; i <= N; i++) {
		f[i] = 1, g[i] = 0;
		for (int j = 1; j <= i; j++) {
			if (a[j] < a[i]) {
				if (f[i] < f[j] + 1) {
					g[i] = j;
					f[i] = f[j] + 1;
				}
			}
		}
	}
	int k = 0;
	for (int i = 1; i <= N; i++) {
		if (f[i] > f[k]) k = i;
	}
	printf("%d\n", f[k]);
	for (int i = 0, len = f[k]; i < len; i++) {
		printf("%d ", a[k]);
		k = g[k];
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

优化版：

void solve() {
	fill(f, f + N, INF);
	for (int i = 1; i <= N; i++) {
		*lower_bound(f, f + N, a[i]) = a[i];
	}
	printf("%d\n", lower_bound(f, f + N, INF) - f);
}
1
2
3
4
5
6
7

1016. 最大上升子序列和

• 题意：找一个上升子序列，是它的和是最大的。

for (int i = 1; i <= N; i++) {
	f[i] = a[i];
	for (int j = 1; j <= i; j++) {
		if (a[j] < a[i]) f[i] = max(f[i], f[j] + a[i]);
	}
}
int ans = 0;
for (int i = 1; i <= N; i++) ans = max(ans, f[i]);
1
2
3
4
5
6
7
8

1010. 拦截导弹

• 题意：定义大于等于的偏序关系，问这样的偏序关系最少可以分为几条链。

法一：狄尔沃斯定理

• 结论一：求最长不下降子序列，只需要把求 LIS 的 lower_bound 改为 upper_bound 就行。
• 结论二：求偏序集的最少链数，就是求在一个序列中，最少可以划分出几个不下降子序列。答案就是最大递减子序列的长度，即把数组反向后求最大上升子序列的长度。
• while (scanf("%d", &a[++N]) != -1);小心！如果这样读入的话，那么 N 的值会比实际情况多1。因为最后一次循环虽然没有读入数据，但是 N 仍然增加了1.

#include
#include
#include
using namespace std;
const int maxn = 1010, INF = 0x3f3f3f3f;
int a[maxn], f[maxn], N;
int main() {
	int x;
	while (scanf("%d", &x) != -1) {
		a[N++] = x;
	}
	memset(f, 0x3f, sizeof f);
	for (int i = 0; i < N; i++) {
		*lower_bound(f, f + N, a[i]) = a[i];
	}
	int ans2 = lower_bound(f, f + N, INF) - f;

	reverse(a, a + N);
	memset(f, 0x3f, sizeof f);
	for (int i = 0; i < N; i++) {
		*upper_bound(f, f + N, a[i]) = a[i];
	}
	int ans1 = lower_bound(f, f + N, INF) - f;
	
	printf("%d\n%d\n", ans1, ans2);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

法二：贪心

• 贪心策略：从前往后扫描。对于每个数：
  情况1：如果现有的子序列结尾都小于当前数，则创建新子序列。
  情况2：将当前数放到结尾大于等于它的最小的子序列后面。

int cnt = 0;
for (int i = 0; i < N; i++) {
	int k = 0;
	//其实，f一定是单调上升的。这个和最长上升子序列贪心解法是等价的。
	while (k < cnt && f[k] < a[i]) k++;
	f[k] = a[i];
	if (k >= cnt) cnt++;
}
printf("%d\n", cnt);
1
2
3
4
5
6
7
8
9

187. 导弹防御系统

• 题意：一套防御系统的导弹拦截高度要么一直 严格单调 上升要么一直 严格单调 下降。给定即将袭来的一系列导弹的高度，请你求出至少需要多少套防御系统，就可以将它们全部击落。

• 这个题很妙的地方是，巧用贪心，up数组一定是单调递减的，如果一个数字可以放进来，一定要放到尽可能考前的组里面去。

法一：朴素的暴搜

#include
#include
#include
using namespace std;
const int maxn = 55;
int a[maxn], up[maxn], down[maxn], ans, N;
void dfs(int u, int su, int sd) {
	if (su + sd >= ans) return;
	if (u == N) {
		ans = su + sd;
		return;
	}
	//放在上升序列里面，这个序列存的是所有上升序列的末尾的值。
	int k = 0;
	while (k < su && up[k] >= a[u]) k++;  //注意这个up是单调下降的
	int t = up[k];
	up[k] = a[u];
	if (k < su) dfs(u + 1, su, sd);
	else dfs(u + 1, su + 1, sd);
	up[k] = t;

	//放在下降序列里面，这个序列存的是所有下降序列的末尾的值。
	k = 0;
	while (k < sd && down[k] <= a[u]) k++;  //注意这个down是单调上升的。
	t = down[k];
	down[k] = a[u];
	if (k < sd) dfs(u + 1, su, sd);
	else dfs(u + 1, su, sd + 1);
	down[k] = t;
}
int main() {
	while (scanf("%d", &N) && N) {
	    //不用将up和down初始化。回溯法原本就回溯到的初始态，而且这道题有su和sd的限制，不用初始化。
		ans = N;
		for (int i = 0; i < N; i++) {
			scanf("%d", &a[i]);
		}
		dfs(0, 0, 0);
		printf("%d\n", ans);
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

法二：迭代加深

#include
#include
#include
using namespace std;
const int maxn = 55;
int a[maxn], up[maxn], down[maxn], N;
bool dfs(int u, int su, int sd, int max_depth) {
	if (su + sd > max_depth) return false;
	if (u == N) return true;

	//放在上升序列里面
	int k = 0;
	while (k < su && up[k] >= a[u]) k++;
	int t = up[k];
	up[k] = a[u];
	if (k < su && dfs(u + 1, su, sd, max_depth)) return true;
	if(k >= su && dfs(u + 1, su + 1, sd, max_depth)) return true;
	up[k] = t;

	//放在下降序列里面
	k = 0;
	while (k < sd && down[k] <= a[u]) k++;
	t = down[k];
	down[k] = a[u];
	if (k < sd && dfs(u + 1, su, sd, max_depth)) return true;
	if (k >= sd && dfs(u + 1, su, sd + 1, max_depth)) return true;
	down[k] = t;

	return false;
}
int main() {
	while (scanf("%d", &N) && N) {
		for (int i = 0; i < N; i++) {
			scanf("%d", &a[i]);
		}
		int depth = 1;
		while(!dfs(0, 0, 0, depth)) depth++;
		printf("%d\n", depth);
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

272. 最长公共上升子序列

• 求 $A$ 和 $B$ 的最长公共上升子序列，$n\le 3000.$

• 设 $f(i,j)$ 为 $a$ 的前 $i$ 项，$b$ 的前 $j$ 项，且以 $b[j]$ 结尾的最长公共上升子序列. 难点在于当 $a[i]=b[j]$ 时迅速找到所有满足 $b[k]<b[j]$ 的 f(i. k) 的最大值. 但是我们注意到 $a[i]=b[j]$，因此只需找到 $b[k]<a[i]$ 且 $f(i,k)$ 最大值即可。这个可以在每一层 $i$ 固定的循环中记录下来，$f(i,j)$ 可以从这个地方转移过来.

• 当 $f(i,j)$ 不包含 $a[i]$ 时，$f(i,j)=f(i-1,j)$；当包含 $a[i]$ 时， f ( i , j ) = m a x { f ( i , 1 ) , f ( i , 2 ) . . . f ( i , j − 1 ) } + 1 f(i, j) = max\{f(i, 1), f(i, 2) ... f(i,j-1)\}+1 f(i,j)=max{f(i,1),f(i,2)...f(i,j−1)}+1.

朴素版（TLE）

for (int i = 1; i <= N; i++) {
	for (int j = 1; j <= N; j++) {
		f[i][j] = f[i - 1][j];
		if (a[i] == b[j]) {
			f[i][j] = max(f[i][j], 1);
			for (int k = 1; k < j; k++) {
				if (b[k] < b[j]) f[i][j] = max(f[i][j], f[i][k] + 1);
			}
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11

优化版

#include
#include
using namespace std;
const int maxn = 3010;
int N, a[maxn], b[maxn], f[maxn][maxn];
int main() {
	scanf("%d", &N);
	for (int i = 1; i <= N; i++) scanf("%d", &a[i]);
	for (int j = 1; j <= N; j++) scanf("%d", &b[j]);
	for (int i = 1; i <= N; i++) {
		//maxv 表示所有 a[i] > b[k](k从1到j-1)的f[i][j] + 1的最大值。
		int maxv = 1;
		for (int j = 1; j <= N; j++) {
			f[i][j] = f[i - 1][j];
			if (a[i] == b[j]) f[i][j] = max(f[i][j], maxv);
			if (b[j] < a[i]) maxv = max(maxv, f[i][j] + 1);
		}
	}
	int ans = 0;
	for (int j = 1; j <= N; j++) ans = max(ans, f[N][j]);
	printf("%d\n", ans);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

（3）最长公共子序列（LCS）

模板题

• 两个序列的问题，一般可以开二维数组，$f(i,j)$ 是第一个序列前 $i$ 项，第二个序列前 $j$ 项组成的两个序列对应的答案。这里的是目前所求出的公共子序列在第一个序列前 $i$ 个数中出现，在第二个序列前 $j$ 个数中出现。
  这个涉及到字符串的题目一定要小心，因为下标是从1开始读的，因此读入的时候要读到 $s+1$ 的位置。
• $s_1...s_i$ 和 $t_1...t_j$ 的公共子列可能是：

1. $s_1...s_{i-1}$ 和 $t_1...t_{j-1}$ 的公共子列末尾追加 $s_i$，当且仅当 $s_i=t_j$.
2. $s_1...s_{i-1}$ 和 $t_1...t_j$ 的公共子列
3. $s_1...s_i$ 和 $t_1...t_{j-1}$ 的公共子列。

#include
#include
using namespace std;
const int maxn = 1010;
int f[maxn][maxn], N, M;
char s1[maxn], s2[maxn];
void solve() {
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			if (s1[i] == s2[j]) f[i][j] = f[i - 1][j - 1] + 1;
			else f[i][j] = max(f[i - 1][j], f[i][j - 1]);
		}
	}
	printf("%d\n", f[N][M]);
}
int main() {
	scanf("%d%d%s%s", &N, &M, s1 + 1, s2 + 1);
	solve();
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

（4）最短编辑距离

模板题

题意：给定两个字符串 $A$ 和 $B$，现在要将 $A$ 经过若干操作变为 $B$，可进行的操作有：

1. 删除–将字符串 $A$ 中的某个字符删除。
2. 插入–在字符串 $A$ 的某个位置插入某个字符。
3. 替换–将字符串 $A$ 中的某个字符替换为另一个字符。

现在请你求出，将 $A$ 变为 $B$ 至少需要进行多少次操作。

• 设 $f(i,j)$ 为把 $A$ 的前 $i$ 个字符变成 $B$ 的前 $j$ 个字符需要的最少操作步骤.
  • 若 $a[i]=b[j]$，则 $f(i,j)=f(i-1,j-1)$.
  • 若 $a[i]\ne b[j]$
    • 可以先删掉 $a[i]$，然后从 $a[1:i-1]$ 变成 $b[i:j]$，即 $f(i-1,j)+1$.
    • 先从 $a[1:i]$ 变成 $b[1:j-1]$，然后在结尾加上 $b[j]$，即 $f(i,j-1)+1$.
    • 可以把 $a[1:i-1]$ 变为 $b[1:j-1]$，然后把 $a[i]$ 变为 $b[j]$，即 $f(i-1,j-1)+1$.
• 一定要注意动态规划遇到字符串时，读取到 $s+1$ 的位置。

void solve() {
	for (int i = 0; i <= N; i++) f[i][0] = i;
	for (int j = 0; j <= M; j++) f[0][j] = j;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
		 //第一个是删（本来i-1和j匹配，删掉第i位使其继续匹配），第二个是增（本来是i和j-1匹配，在增加一个和第j位匹配）。
			f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);  
			if (a[i] == b[j]) f[i][j] = min(f[i][j], f[i - 1][j - 1]);  //相等，直接到下一位
			else f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);   //替换
		}
	}
	printf("%d\n", f[N][M]);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

4.记忆化搜索

901. 滑雪

• 拓扑排序 + 记忆化搜索
• 这里的 $f(x,y)$ 的意思是，从 $(x,y)$ 这个点出发，能够下滑的最大距离是多少。这样的话，每次发现一个比 $(x,y)$ 高的一个点，就可以将这个点对应的 f 值更新为 $max(f,f(x,y)+1)$.

#include
#include
#include
using namespace std;
const int maxn = 310;
int N, M, f[maxn][maxn], h[maxn][maxn];
int dx[] = { 1, -1, 0, 0 }, dy[] = { 0, 0, 1, -1 };
int dp(int x, int y) {
	int& v = f[x][y];
	if (v != -1) return v;
	v = 1;
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i], ny = y + dy[i];
		if (1 <= nx && nx <= N && 1 <= ny && ny <= M && h[nx][ny] < h[x][y]) {
			v = max(v, dp(nx, ny) + 1);
		}
	}
	return v;
}
int main() {
	scanf("%d%d", &N, &M);
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			scanf("%d", &h[i][j]);
		}
	}
	memset(f, -1, sizeof f);
	int res = 0;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			res = max(res, dp(i, j));
		}
	}
	printf("%d\n", res);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

5.状态机模型

基本概念

简介

OI 中所说的“自动机”一般都指“确定有限状态自动机”。

自动机是一个对信号序列进行判定的数学模型。

“信号序列”是指一连串有顺序的信号（数组从 $1$ 到 $n$，字符串从前到后每一个字符等），“判定”是指针对某一个命题给出或真或假的回答。自动机只是一个 数学模型，而 不是算法，也 不是数据结构。实现同一个自动机的方法有很多种，可能会有不一样的时空复杂度。

形式化定义

一个 确定有限状态自动机（DFA） 由以下五部分构成：

1. 字符集（$\Sigma$），该自动机只能输入这些字符。
2. 状态集合（$Q$）。如果把一个 DFA 看成一张有向图，那么 DFA 中的状态就相当于图上的顶点。
3. 起始状态（$start$），$start\in Q$，是一个特殊的状态。起始状态一般用 $s$ 表示，为了避免混淆，本文中使用 $start$。
4. 接受状态集合（$F$），$F\subseteq Q$，是一组特殊的状态。
5. 转移函数（$\delta$），$\delta$ 是一个接受两个参数返回一个值的函数，其中第一个参数和返回值都是一个状态，第二个参数是字符集中的一个字符。如果把一个 DFA 看成一张有向图，那么 DFA 中的转移函数就相当于顶点间的边，而每条边上都有一个字符。

DFA 的作用就是识别字符串，一个自动机 $A$，若它能识别（接受）字符串 $S$，那么 $A(S)=\mathrm{True}$，否则 $A(S)=\mathrm{False}$。

当一个 DFA 读入一个字符串时，从初始状态起按照转移函数一个一个字符地转移。如果读入完一个字符串的所有字符后位于一个接受状态，那么我们称这个 DFA 接受 这个字符串，反之我们称这个 DFA 不接受 这个字符串。

如果一个状态 $v$ 没有字符 $c$ 的转移，那么我们令 $\delta (v,c)=\mathrm{null}$，而 $\mathrm{null}$ 只能转移到 $\mathrm{null}$，且 $\mathrm{null}$ 不属于接受状态集合。无法转移到任何一个接受状态的状态都可以视作 $\mathrm{null}$，或者说，$\mathrm{null}$ 代指所有无法转移到任何一个接受状态的状态。

我们扩展定义转移函数 $\delta$，令其第二个参数可以接收一个字符串：$\delta (v,s)=\delta (\delta (v,s[1]),s[2..|s|])$，扩展后的转移函数就可以表示从一个状态起接收一个字符串后转移到的状态。那么，$A(s)=[\delta (start,s)\in F]$。

OI 中常用的自动机

字典树

字典树 是大部分 OIer 接触到的第一个自动机，接受且仅接受指定的字符串集合中的元素。

转移函数就是 Trie 上的边，接受状态是将每个字符串插入到 Trie 时到达的那个状态。

KMP 自动机

KMP 算法 可以视作自动机，基于字符串 $s$ 的 KMP 自动机接受且仅接受以 $s$ 为后缀的字符串，其接受状态为 $|s|$。

转移函数：

δ ( i , c ) = { i + 1 s [ i + 1 ] = c 0 s [ 1 ] ≠ c ∧ i = 0 δ ( π ( i ) , c ) s [ i + 1 ] ≠ c ∧ i > 0 \delta(i, c)=

δ(i,c)=⎩ ⎨ ⎧​i+10δ(π(i),c)​s[i+1]=cs[1]=c∧i=0s[i+1]=c∧i>0​

AC 自动机

AC 自动机 接受且仅接受以指定的字符串集合中的某个元素为后缀的字符串。也就是 Trie + KMP。

后缀自动机

后缀自动机 接受且仅接受指定字符串的后缀。

广义后缀自动机

广义后缀自动机 接受且仅接受指定的字符串集合中的某个元素的后缀。也就是 Trie + SAM。

广义 SAM 与 SAM 的关系就是 AC 自动机与 KMP 自动机的关系。

回文自动机

回文自动机 比较特殊，它不能非常方便地定义为自动机。

如果需要定义的话，它接受且仅接受某个字符串的所有回文子串的 中心及右半部分。

“中心及右边部分”在奇回文串中就是字面意思，在偶回文串中定义为一个特殊字符加上右边部分。这个定义看起来很奇怪，但它能让 PAM 真正成为一个自动机，而不仅是两棵树。

序列自动机

序列自动机 接受且仅接受指定字符串的子序列。

1049. 大盗阿福

• 题意：街上一共有 $N$ 家店铺，不能抢劫相邻两家的店铺，问收益最大值。
• $f(i,j)$：走到了第 $i$ 步，且状态为 j 时，收益最大值。$j=0$ 表示没有抢第 $i$ 家店，$j=1$ 表示抢了第 $i$ 家店。
• f ( i , 0 ) = m a x { f ( i − 1 , 0 ) , f ( i − 1 , 1 ) } f(i, 0) = max\{f(i-1, 0),f(i-1,1)\} f(i,0)=max{f(i−1,0),f(i−1,1)}
• $f(i,1)=f(i-1,0)+w[i]$.

#include
#include
using namespace std;
const int maxn = 100010, INF = 0x3f3f3f3f;
int f[maxn][2], w[maxn], N;
int main() {
	int T;
	scanf("%d", &T);
	f[0][0] = 0, f[0][1] = -INF;
	while (T--) {
		scanf("%d", &N);
		for (int i = 1; i <= N; i++) scanf("%d", &w[i]);
		for (int i = 1; i <= N; i++) {
			f[i][0] = max(f[i - 1][0], f[i - 1][1]);
			f[i][1] = f[i - 1][0] + w[i];
		}
		printf("%d\n", max(f[N][0], f[N][1]));
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

1052. 设计密码

• 给定一个字符串 $T$，和一个整数 $N$
  现需设计一个密码 $S$, $S$ 需满足：

  $S$ 的长度是 $N$, $N\le 50$
  $S$ 只包含小写英文字母
  $S$ 不包含子串 $T$
  求该密码的 方案数，答案对 $10^9+7$ 取模

考虑 KMP 自动机转移函数
δ ( i , c ) = { i + 1 s [ i + 1 ] = c 0 s [ 1 ] ≠ c ∧ i = 0 δ ( π ( i ) , c ) s [ i + 1 ] ≠ c ∧ i > 0 \delta(i, c)=

δ(i,c)=⎩ ⎨ ⎧​i+10δ(π(i),c)​s[i+1]=cs[1]=c∧i=0s[i+1]=c∧i>0​
因此，对于主串的第 $i$ 个字符，有 $26$ 中取值 $a\sim z$，每一种取值（回忆 KMP 匹配过程），都可以跳到模式串的某一个位置。

因此，可以对模式串搭建一个 KMP 自动机，输入的有序信号序列就是主串，状态集合即为模式串的每一个字符，转移函数相当于主串对应的字符，起始状态是模式串第 $0$ 个，接受态是第 $0$ 到第 $m-1$ 个位置，第 $m$ 个位置不是接受态，因为如果到了第 $m$ 个位置意味着匹配成功.

#include
using namespace std;
const int N = 55, mod = 1e9 + 7;
int f[N][N], ne[N];
char str[N];
int main()
{
    int n;
    scanf("%d", &n);
    scanf("%s", str + 1);
    int m = strlen(str + 1);
    for(int i = 2, j = 0; i <= n; i++)
    {
        while(j && str[i] != str[j + 1]) j = ne[j];
        if(str[i] == str[j + 1]) j++;
        ne[i] = j;
    }
    f[0][0] = 1;
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < m; j++)
        {
            for(int k = 'a'; k <= 'z'; k++)
            {
                int u = j;
                while(u && k != str[u + 1]) u = ne[u];
                if(k == str[u + 1]) u++;
                if(u < m) f[i + 1][u] = (f[i + 1][u] + f[i][j]) % mod;
            }
        }
    }
    int ans = 0;
    for(int i = 0; i < m; i++) ans = (ans + f[n][i]) % mod;
    printf("%d\n", ans);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

1053. 修复DNA

• 题意：把一个长度为 $m(m\le 1000)$ 的主串，给定 $n(n\le 50)$ 个长度不超过20的字符串集合 { S } \{S\} {S}。要求修改尽可能少的主串字母，使得主串中不含 { S } \{S\} {S} 中的任何字符串.
• $f(i,j)$ 前 $i$ 个位置，走到模式串的第 $j$ 个位置，最少修改字母的数量.

#include
using namespace std;
const int N = 1010;

int get(char c)
{
    if(c == 'A') return 0;
    if(c == 'G') return 1;
    if(c == 'T') return 2;
    return 3;
}

int tr[N][4], ne[N], dar[N], idx;
char str[N];
int n, kase, q[N];

void insert()
{
    int p = 0;
    for(int i = 0; str[i]; i++)
    {
        int k = get(str[i]);
        if(!tr[p][k]) tr[p][k] = ++idx;
        p = tr[p][k];
    }
    dar[p] = 1;
}

void build()
{
    int hh = 0, tt = -1;
    for(int k = 0; k < 4; k++)
    {
        if(tr[0][k]) q[++tt] = tr[0][k];
    }
    while(hh <= tt)
    {
        int t = q[hh++];
        for(int k = 0; k < 4; k++)
        {
            int p = tr[t][k];
            if(!p) tr[t][k] = tr[ne[t]][k];
            else
            {
                ne[p] = tr[ne[t]][k];
                q[++tt] = p;
                dar[p] |= dar[ne[p]];
            }
        }
    }
}
int f[N][N];
int main()
{
    while(cin >> n, n)
    {
        memset(tr, 0, sizeof tr);
        memset(ne, 0, sizeof ne);
        memset(dar, 0, sizeof dar);
        idx = 0;
        for(int i = 1; i <= n; i++)
        {
            scanf("%s", str);
            insert();
        }
        build();
        scanf("%s", str + 1);
        int m = strlen(str + 1);
        
        memset(f, 0x3f, sizeof f);
        f[0][0] = 0;
        for(int i = 0; i < m; i++)
        {
            for(int j = 0; j <= idx; j++)
            {
                for(int k = 0; k < 4; k++)
                {
                    int t = (get(str[i + 1]) != k);
                    int p = tr[j][k];
                    if(!dar[p]) f[i + 1][p] = min(f[i + 1][p], f[i][j] + t);
                }
            }
        }
        int res = 0x3f3f3f3f;
        for(int i = 0; i <= idx; i++)
        {
            res = min(res, f[m][i]);
        }
        if(res == 0x3f3f3f3f) res = -1;
        printf("Case %d: %d\n", ++kase, res);
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94

6.状态压缩DP

棋盘式（基于连通性）

蒙德里安的梦想

• 求把 $N\ast M$ 的棋盘分割成若干个 $1\ast 2$ 的长方形的方案数。
• 把横向的放完之后，纵向长方形的摆放就确定了。$f(i,j)$ 记录第 $i$ 列的摆放状态 $j$，$j$ 就是一个 $N$ 位二进制数。当第 $k$ 行上面横着摆放了放了长方形时（并且必须放的是正方形的左半部分）， $j$ 的第 $k$ 位就是 $1$，反之就是 $0$. 不过竖着拜访
• $k$ 就是第 $i-1$ 列的状态。本列的每一个状态都由上列所有“合法”状态转移过来 $f[i][j]+=f[i-1][k]$.
• 那么对于第 $i$ 列，我们可以枚举状态 $j$，看看哪些是合法的。对于第 $i-1$ 列的状态 k，我们发现 $j\&k==0$ 且 $j|k$ 不存在连续奇数个 $0$，那么这个状态就是合法的。
• 列的是从 $0$ 开始开始的。
• 有一个易错点。代码中有一个是预处理过程，但是这样处理（总共只预处理一遍）是不对的：

for (int i = 0; i < maxm; i++) {
    int cnt = 0;
    st[i] = true;
    for (int j = 0; j < maxn; j++) {
        if (i >> j & 1) {
            if (cnt & 1) st[i] = false;
            cnt = 0;
        }
        else cnt++;
    }
    if (cnt & 1) st[i] = false;
}
1
2
3
4
5
6
7
8
9
10
11
12

• 错误的原因在于状态的前导0是有意义的。而这样子相当于所有状态都是12位的数字，即地图全部是12行了。

const int maxn = 12;
const int maxm = 1 << 12;
bool st[maxm];  //表示一种二进制状态是否存在连续的奇数个0.
int N, M;
long long f[maxn][maxm];  //强调，f第一维存的是列，第二维存的是二进制状态。
void solve() {
	memset(f, 0, sizeof f);
    
    //这一步是预处理，看看某一个二进制数字有没有连续奇数个0，有的话st就是false，反之就是true.
	for (int i = 0; i < 1 << N; i++) {
		int cnt = 0;
		st[i] = true;
		for (int j = 0; j < N; j++) {
			if (i >> j & 1) {
				if (cnt & 1) st[i] = false;
				cnt = 0;
			}
			else cnt++;
		}
		if (cnt & 1) st[i] = false;
	}
	f[0][0] = 1;  //因为第一列全是0属于一种情况，上一列还没有捅过来小方格。
	//注意，列的下标从0开始，第一列不需要枚举。
	for (int i = 1; i <= M; i++) {
		for (int j = 0; j < 1 << N; j++) {
			for (int k = 0; k < 1 << N; k++) {
				if ((j & k) == 0 && st[j | k]) f[i][j] += f[i - 1][k];
			}
		}
	}
	//第M + 1列的全0状态就是方案数，就是左边一个小方格也不能捅过来（即第M + 1列什么也别放）
	printf("%lld\n", f[M][0]);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

1064. 小国王

• 题意： 在 $n\times n$ 的棋盘上放 $k$ 个国王，国王可攻击相邻的 $8$ 个格子，求使它们无法互相攻击的方案总数。
• $f(i,j,s)$: 只摆在前 $i$ 行，已经摆了 $j$ 个国王，并且第 $i$ 行摆放的状态是 $j$ 的方案数。$s$ 就是一个二进制串，摆放是 $1$，没有摆放是 $0$。为什么这次需要一个 $j$ 呢？因为这道题国王的数量有限制，最多摆放 $k$ 个。
• 需要满足的条件：

1. 第 $i-1$ 行不能有两个相邻的1；
2. 第 $i-1$ 行和第 $i$ 行不能起冲突：$(a\&b)==0$ 且 $a\&b$ 不能有两个相邻的1.

• 状态压缩 $dp$ 时间复杂度估算的时候都会有点高，但实际上合法方案的数量并不多，因此实际上并没有那么高。
• 注意，状态压缩 $dp$ 求方案数很容易爆 $int$，别忘用 long long.

#include
#include
#include
#include
using namespace std;
//maxn 开到 12 的原因是，第 0 行不用，答案应该是 f(N + 1, K, 0), 即第 N + 1 行什么也不摆。
const int maxn = 12, maxm = 1 << 10, maxk = 110;
int N, K;
vector<int> state;  //储存所有合法状态。

int cnt[maxm]; //储存每一个状态的1的个数。
vector<int> head[maxm];  //每一个状态可以转移到的其他状态。

typedef long long ll;
ll f[maxn][maxk][maxm]; //状态的方案数。

//检查这个状态是不是存在连续的两个1.有两个1返回false，没有的话返回true.
bool check(int st) {
	for (int i = 0; i < N; i++) {
		if ((st >> i & 1) && (st >> i + 1 & 1)) return false;
	}
	return true;
}
//计算该状态有多少个1
int calculate(int st) {
	int res = 0;
	for (int i = 0; i < N; i++) res += st >> i & 1;
	return res;
}
int main() {
	cin >> N >> K;
	//预处理所有状态。
	for (int i = 0; i < 1 << N; i++) {
		if (check(i)) {
			state.push_back(i);
			cnt[i] = calculate(i);  //计算该状态有多少个1，其实就是计算该状态有多少个国王。
		}
	}

	for (int i = 0; i < state.size(); i++) {
		for (int j = 0; j < state.size(); j++) {
			int a = state[i], b = state[j];
			if ((a & b) == 0 && check(a | b)) {
            //这份代码种的 head 索引和值均为state。
				head[a].push_back(b);
			}
		}
	}

	f[0][0][0] = 1;
	for (int i = 1; i <= N + 1; i++) {
		for (int j = 0; j <= K; j++) {
			for (int k = 0; k < state.size(); k++) {
				int a = state[k];
				for (auto b : head[a]) {
					//b本身就是状态，不是state中的下标
					int c = cnt[a];
					if (j >= c) f[i][j][b] += f[i - 1][j - c][a];
				}
			}
		}
	}

	//最后答案是 f(N + 1, K, 0), 即第 N + 1 行什么也不摆，这就是最后的方案总数。
	cout << f[N + 1][K][0] << endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

327. 玉米田

• 题意：农夫约翰的土地由 $M\ast N$ 个小方格组成，现在他要在土地里种植玉米。部分土地是不育的，无法种植。而且，相邻的土地不能同时种植玉米，也就是说种植玉米的所有方格之间都不会有公共边缘。现在给定土地的大小，请你求出共有多少种种植方法。

• 我们一行一行地摆，那么正在摆的这一行只和上一行有关系。这个和小国王那个题很相似。

• $f(i,j)$：摆了前 $i$ 行，且第 $i$ 行的状态是 $j$ 的方案数。假设第 $i-1$ 行的状态是 a，第 $i$ 行的状态是 $b$。合法的状态是：

1. $a,b$ 不可以有两个相邻的 1。
2. $(a\&b)==1$.
3. $a,b$ 与这一行禁止摆放的状态 $a_0,b_0$ 不可以有相同位置的0. 比如 $a\&a_0\ne 0$ 且 $b\&b_0\ne 0$.

#include
#include
#include
#include
using namespace std;
//maxn 开到14和小国王那道题是一样的。
const int maxn = 14, maxm = 1 << 12, mod = 1e8;

int N, M;
//g 表示第 i 行的禁止摆放的状态。
int g[maxn];
vector<int> state;
vector<int> head[maxm];
int f[maxn][maxm];

// 检查一个状态有无相邻的两个1. 有的话返回false, 没有的话返回 true.
bool check(int st) {
	for (int i = 0; i < M; i++) {
		if ((st >> i & 1) && (st >> i + 1 & 1)) {
			return false;
		}
	}
	return true;
}
int main() {
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		for (int j = 0; j < M; j++) {
			int t;
			cin >> t;
			g[i] += !t << j;
		}
	}
	for (int i = 0; i < 1 << M; i++) {
		if (check(i)) {
			state.push_back(i);
		}
	}

	//head保存的是state，不是下标。
	for (int i = 0; i < state.size(); i++) {
		for (int j = 0; j < state.size(); j++) {
			int a = state[i], b = state[j];
			if ((a & b) == 0) {
				head[a].push_back(b);
			}
		}
	}
	f[0][0] = 1;
	for (int i = 1; i <= N + 1; i++) {
		for (int j = 0; j < state.size(); j++) {
			int a = state[j];
			for (int b : head[a]) {
                //非法位置不能放东西.
				if ((g[i] & b) == 0) f[i][b] = (f[i][b] + f[i - 1][a]) % mod;
			}
		}
	}
	cout << f[N + 1][0] << endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

集合式

最短Hamilton路径

• 旅行商问题
• $f[i,j]$：所有包含顶点 $k$ 且终点到 $j$ 的路径的最短长度（显然，$j$ 之前的路径是不包含 $j$ 的）。就是从 $k$ 走到 $j$，$k$ 是 $j$ 的前驱节点。$i$ 是所经路径的状态，是一串二进制数字，第 $u$ 位是 $1$ 表示经过这个节点，是 $0$ 表示没经过这个节点。
• 这道题有一个性质，就是从小到大枚举路径状态，在计算一个状态 $A$ 的最短路时，任意扣掉一个 $1$ 的状态 $B$ 在之前都计算过了，因为 $A>B$.

const int maxn = 20, maxm = 1 << maxn;
int f[maxm][maxn], w[maxn][maxn];
void solve() {
	memset(f, 0x3f, sizeof f);
	f[1][0] = 0;
	for (int i = 0; i < 1 << N; i++) {
		for (int j = 0; j < N; j++) {
			if (i >> j & 1) {
				for (int k = 0; k < N; k++) {
                    //之前的路径不可以经过j。因为要不重不漏的经过每一个节点。
                    //说白了就是路径把j扣掉，因为更新的是第 k 个点，因此状态还要包含k.
					if ((i - (1 << j)) >> k & 1) {
						f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j]);
					}
				}
			}
		}
	}
	printf("%d\n", f[(1 << N) - 1][N - 1]);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

7.区间DP

石子合并

• 设有 $N$ 堆石子。每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和。问总的代价最小是多少。
• 注意这个题是只能合并相邻的两堆石子。

#include
using namespace std;
const int N = 310;
int s[N], f[N][N];
int n;
int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d", &s[i]);
        s[i] += s[i - 1];
    }
    memset(f, 0x3f, sizeof f);
    for(int i = 1; i <= n; i++) f[i][i] = 0;
    
    for(int len = 2; len <= n; len++)
    {
        for(int l = 1, r = l + len - 1; r <= n; l++, r++)
        {
            for(int k = l; k + 1 <= r; k++)
            {
                f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
            }
        }
    }
    printf("%d\n", f[1][n]);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

1068. 环形石子合并

将 $n$ 堆石子绕圆形操场排放，现要将石子有序地合并成一堆。规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆的石子数记做该次合并的得分。请编写一个程序，读入堆数 $n$ 及每堆的石子数，并进行如下计算：

• 选择一种合并石子的方案，使得做 $n-1$ 次合并得分总和最大。
• 选择一种合并石子的方案，使得做 $n-1$ 次合并得分总和最小。

**怎样处理环？**我们将这条链延长两倍，变成 $2\times n$ 堆，其中第 $i$ 堆与第 $n+i$ 堆相同，用动态规划求解后，取 $f(1,n),f(2,n+1),...,f(i,n+i-1)$ 中的最优值，即为最后的答案。时间复杂度 $O(n^3)$。

#include
using namespace std;
const int N = 410, INF = 0x3f3f3f3f;

int f[N][N], g[N][N], s[N], w[N];
int n;
int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d", &w[i]);
        w[n + i] = w[i];
    }

    for(int i = 1; i <= 2 * n; i++) s[i] = s[i - 1] + w[i];
    memset(f, 0x3f, sizeof f);
    memset(g, -0x3f, sizeof g);
    for(int i = 1; i <= 2 * n; i++) f[i][i] = g[i][i] = 0;

    for(int len = 2; len <= n; len++)
    {
        for(int l = 1, r = l + len - 1; r <= 2 * n; l++, r++)
        {
            for(int k = l; k < r; k++)
            {
                f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
                g[l][r] = max(g[l][r], g[l][k] + g[k + 1][r] + s[r] - s[l - 1]);
            }
        }
    }

    int res1 = INF, res2 = -INF;
    for(int l = 1, r = l + n - 1; r <= 2 * n; l++, r++)
    {
        res1 = min(res1, f[l][r]);
        res2 = max(res2, g[l][r]);
    }
    printf("%d\n%d\n", res1, res2);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41