数字三角形
给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
输出格式
输出一个整数，表示最大的路径数字和。
思路：
主要难点是坐标系的建立，三角形的行仍是每一行，列则是从左至右每一条斜边。
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
| #include <cstdio>
#include <algorithm>
using namespace std;
const int N = 510, INF = 1e5;
int val[N][N], f[N][N];
int main()
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= i; ++j)
scanf("%d", &val[i][j]);
for (int i = 0; i <= n; ++i)
for (int j = 0; j <= i + 1; ++j)
f[i][j] = -INF;
f[1][1] = val[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], f[i - 1][j]) + val[i][j];
int res = -INF;
for (int i = 1; i <= n; ++i)
res = max(res, f[n][i]);
printf("%d", res);
return 0;
}
|
最长公共子序列
给定两个长度分别为 $N$ 和 $M$ 的字符串 $A$ 和 $B$，求既是 $A$ 的子序列又是 $B$ 的子序列的字符串长度最长是多少。
数据范围
$1 ≤ N ≤ 1000$
思路：
$f[i][j]$ 表示所有在第一个字符串的前 $i$ 个字符中出现且在第二个字符串前 $j$ 个字符中出现的字符串集合中的最长字符串的长度。
状态划分：两个字符串的最长公共子串是否分别含有第 $i$ 位和第 $j$ 位（$A$ 串 $i$ 位 $B$ 串 $j$ 位）。根据排列组合，可以划分为四种状态。
其中 $0$ 表示不包含该位，$1$ 表示含有该位。事实上，这样划分并不严谨，划分出的状态之间存在交集。如中间两种状态，按照状态方程的含义应当是一定含有 $A[i] \, or \, B[j]$，但事实上此时的最长公共子序列可能不含有这个字符。状态划分的第一项更是直接完全包含于状态二与状态三的并集。
但是由于是求最值，因此重复并不影响结果。
转移方程
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| #include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1010;
char a[N], b[N];
int f[N][N];
int main()
{
int n, m;
scanf("%d%d", &n, &m);
scanf("%s%s", a + 1, b + 1);
for(int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
{
f[i][j] = max(f[i - 1][j], f[i][j - 1]);
if (a[i] == b[j])
f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
}
printf("%d", f[n][m]);
return 0;
}
|
最短编辑距离
给定两个字符串 $A$ 和 $B$，现在要将 $A$ 经过若干操作变为 $B$，可进行的操作有：
- 删除–将字符串A中的某个字符删除。
- 插入–在字符串A的某个位置插入某个字符。
- 替换–将字符串A中的某个字符替换为另一个字符。
现在请你求出，将A变为B至少需要进行多少次操作。
数据范围
$1≤n,m≤1000$
思路：
$f[i][j]$表示所有第一个字符串的前 $i$ 个字符编辑成第二个字符串的前 $j$ 个字符时所有的编辑方法中操作次数最少的方法的操作次数。
状态划分：根据最后一次操作的类型进行划分。
以删除为例：$A$ 需要删除掉 $A[i]$ 才能与 $B$的前 $j$ 个匹配，因此此时有 $A[0 \rightarrow i-1]$ 已经与 $B[0 \rightarrow j]$ 匹配。因此有 $f[i][j] = f[i - 1][j] + 1$。
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
| #include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1010, INF = 2e3;
char a[N], b[N];
int f[N][N];
int main()
{
int n, m;
scanf("%d%s%d%s", &n, a + 1, &m, b + 1);
for (int i = 0; i <= n; ++i)
for (int j = 0; j <= m; ++j)
f[i][j] = INF;
for (int i = 0; i <= n; ++i)
f[i][0] = i;
for (int i = 0; i <= m; ++i)
f[0][i] = i;
for(int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
{
f[i][j] = min(f[i - 1][j], 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", f[n][m]);
return 0;
}
|