【题目描述】
给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
【输入格式】
第一行包含整数
n
n
n，表示数字三角形的层数。
接下来
n
n
n行，每行包含若干整数，其中第
i
i
i行表示数字三角形第
i
i
i层包含的整数。
【输出格式】
输出一个整数，表示最大的路径数字和。
【数据范围】
1
≤
n
≤
500
1≤n≤500
1≤n≤500
−
10000
≤
三
角
形
中
的
整
数
≤
10000
−10000≤三角形中的整数≤10000
−10000≤三角形中的整数≤10000
【输入样例】
5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5
【输出样例】
30
#include二、最长上升子序列（LIS）#include #include using namespace std; const int N = 510; int a[N][N], f[N][N];//f[i][j]表示所有从起点走到[i, j]的最大值 int n; int main() { cin >> n; for (int i = 1; i <= n; i++) for (int j = 1; j <= i; j++) cin >> a[i][j]; memset(f, 0x8f, sizeof f);//初始化为负无穷 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 res = -0x3f3f3f3f; for (int i = 1; i <= n; i++)//遍历最后一行找出最大值 res = max(res, f[n][i]); cout << res << endl; return 0; }
【题目描述】
给定一个长度为
N
N
N的数列，求数值严格单调递增的子序列的长度最长是多少。
【输入格式】
第一行包含整数
N
N
N。
第二行包含
N
N
N个整数，表示完整序列。
【输出格式】
输出一个整数，表示最大长度。
【数据范围】
朴素版
1
≤
N
≤
1000
1≤N≤1000
1≤N≤1000
−
1
0
9
≤
数
列
中
的
数
≤
1
0
9
−10^9≤数列中的数≤10^9
−109≤数列中的数≤109
优化版
1
≤
N
≤
100000
1≤N≤100000
1≤N≤100000
−
1
0
9
≤
数
列
中
的
数
≤
1
0
9
−10^9≤数列中的数≤10^9
−109≤数列中的数≤109
【输入样例】
7 3 1 2 1 8 5 6
【输出样例】
4
①：朴素版LIS（ O ( n 2 ) O(n^2) O(n2)）
#include#include using namespace std; const int N = 1010; int a[N], f[N];//f[i]表示以第i个数结尾的LIS长度 int n, res; int main() { cin >> n; for (int i = 0; i < n; i++) cin >> a[i]; for (int i = 0; i < n; i++) { f[i] = 1;//只有a[i]一个数的极端情况 for (int j = 0; j < i; j++) if (a[j] < a[i]) f[i] = max(f[i], f[j] + 1); res = max(res, f[i]); } cout << res << endl; return 0; }
②：优化版LIS（ O ( n l o g n ) O(nlogn) O(nlogn)）
#include三、最长公共子序列（LCS）using namespace std; const int N = 100010; int a[N], f[N];//f表示以最小的数结尾的LIS int n, cnt;//cnt记录f的长度，即LIS的长度 int main() { cin >> n; for (int i = 0; i < n; i++) cin >> a[i]; f[cnt++] = a[0]; for (int i = 1; i < n; i++) { //若a[i] ≥ f[cnt - 1]则说明可使LIS长度+1，因此加入LIS中 if (a[i] > f[cnt - 1]) f[cnt++] = a[i]; else { //二分查找第一个大于等于a[i]的数，将其替换为a[i] int l = 0, r = cnt - 1; while (l < r) { int mid = l + r >> 1; if (f[mid] >= a[i]) r = mid; else l = mid + 1; } f[r] = a[i]; } } cout << cnt << endl; return 0; }
【题目描述】
给定两个长度分别为
N
N
N和
M
M
M的字符串
A
A
A和
B
B
B，求既是
A
A
A的子序列又是
B
B
B的子序列的字符串长度最长是多少。
【输入格式】
第一行包含两个整数
N
N
N和
M
M
M。
第二行包含一个长度为
N
N
N的字符串，表示字符串
A
A
A。
第三行包含一个长度为
M
M
M的字符串，表示字符串
B
B
B。
字符串均由小写字母构成。
【输出格式】
输出一个整数，表示最大长度。
【数据范围】
1
≤
N
,
M
≤
1000
1≤N,M≤1000
1≤N,M≤1000
【输入样例】
4 5 acbd abedc
【输出样例】
3
#include四、最短编辑距离#include using namespace std; const int N = 1010; char a[N], b[N]; int f[N][N]; int n, m; int main() { cin >> n >> m >> 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); } cout << f[n][m] << endl; return 0; }
【题目描述】
给定两个字符串
A
A
A和
B
B
B，现在要将
A
A
A经过若干操作变为
B
B
B，可进行的操作有：
删除：将字符串
A
A
A中的某个字符删除。
插入：在字符串
A
A
A的某个位置插入某个字符。
替换：将字符串
A
A
A中的某个字符替换为另一个字符。
现在请你求出，将
A
A
A变为
B
B
B至少需要进行多少次操作。
【输入格式】
第一行包含整数
n
n
n，表示字符串
A
A
A的长度。
第二行包含一个长度为
n
n
n的字符串
A
A
A。
第三行包含整数
m
m
m，表示字符串
B
B
B的长度。
第四行包含一个长度为
m
m
m的字符串
B
B
B。
字符串中均只包含大写字母。
【输出格式】
输出一个整数，表示最少操作次数。
【数据范围】
1
≤
n
,
m
≤
1000
1≤n,m≤1000
1≤n,m≤1000
【输入样例】
10 AGTCTGACGC 11 AGTAAGTAGGC
【输出样例】
4
#include#include using namespace std; const int N = 1010; char a[N], b[N]; int f[N][N];//f[i][j]表示把a的前i个字母变为b的前j个字母的最少操作次数 int n, m; int main() { cin >> n >> a + 1 >> m >> b + 1; //若a的前0个字母和b的前i个字母匹配，则需要增加字符，增加数量与b的长度有关 //若a的前i个字母和b的前0个字母匹配，则需要删除字符，删除数量与a的长度有关 for (int i = 0; i <= m; i++) f[0][i] = i; for (int i = 0; i <= n; i++) f[i][0] = i; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; 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); } cout << f[n][m] << endl; return 0; }
