目录
1 基础知识2 模板3 工程化
1 基础知识
暂无。。。
2 模板
暂无。。。
3 工程化
题目1：最长严格上升子序列，要求时间复杂度为
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn)。
解题思路：保存每个长度下的最小的结尾元素值，遍历数组元素时，通过二分找到它，然后更新它即可，返回len。
该算法的关键步骤如下：
定义向量vec，vec[i]表示所有长度为i+1的上升子序列的集合，该集合当中最后一个元素最小的那个值。很显然可以知道，vec中的元素满足严格单调递增（根据vec[i]的定义即可得到）。遍历原先的数组中的每一个元素x，在vec中找到>=x的第一个元素的下标idx：如果这个下标不存在，往vec中插入元素x；否则vec[idx] = x。
C++代码如下，
#include
#include
using namespace std;
const int N = 1e5 + 10;
int n;
int a[N];
int main() {
cin >> n;
for (int i = 0; i < n; ++i) cin >> a[i];
vector
for (int i = 0; i < n; ++i) {
//在vec中找到>=a[i]的第一个元素的下标
int idx = lower_bound(vec.begin(), vec.end(), a[i]) - vec.begin();
if (idx == vec.size()) {//表示没有找到
vec.emplace_back(a[i]);
} else {
vec[idx] = a[i];
}
}
cout << vec.size() << endl;
return 0;
}
题目1扩展1：求最长严格下降子序列。要求算法时间复杂度为
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn)。
解题思路：将原先数组reverse一遍，等价于题目1。
题目2：最小编辑距离。有三种操作，插入、删除和替换，求将字符串a变成字符串b的最小操作次数。
解题思路：DP，考虑最后一次操作次数。
状态定义，f[i][j]：将字符串a的前i位变为字符串b的前j位的最小操作次数。
状态转移，有
最后一次操作是插入操作，则说明操作前已经匹配了字符串b的前j-1位，故f[i][j - 1] + 1。最后一次操作是删除操作，则说明操作前字符串a的前i-1位已经匹配了字符串b的前j位，故f[i - 1][j] + 1。最后一次操作是替换操作，则说明操作前字符串a的前i-1位已经匹配了字符串b的前j-1位，但可能a[i] == b[j]，则f[i - 1][j - 1]；否则f[i - 1][j - 1] + 1。
初始化，f[i][0]表示将a的前i位变成b的前0位，则值为i。f[0][j]表示将a的前0位变成b的前j位，则值为j。
最终答案，f[n][m]。
C++代码为，
#include
using namespace std;
const int N = 1010;
int n, m;
char a[N], b[N];
int f[N][N];
int main() {
cin >> n >> a + 1;
cin >> m >> b + 1;
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) {
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;
}
题目3：编辑距离。
思路：就是将题目2的实现套用过来，调用多次即可。
C++代码如下，
#include
#include
using namespace std;
const int N = 1010, M = 20;
int n, m;
char str[N][M];
int f[M][M];
int get_dis(char a[], char b[]) {
int la = strlen(a + 1), lb = strlen(b + 1);
for (int i = 0; i <= la; ++i) f[i][0] = i;
for (int j = 0; j <= lb; ++j) f[0][j] = j;
for (int i = 1; i <= la; ++i) {
for (int j = 1; j <= lb; ++j) {
f[i][j] = min(f[i-1][j] + 1, f[i][j-1] + 1);
f[i][j] = min(f[i][j], f[i-1][j-1] + (a[i] != b[j]));
}
}
return f[la][lb];
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; ++i) cin >> str[i] + 1;
for (int j = 1; j <= m; ++j) {
int limit;
char b[20];
cin >> b + 1 >> limit;
int res = 0;
for (int i = 1; i <= n; ++i) {
if (get_dis(str[i], b) <= limit) res += 1;
}
cout << res << endl;
}
return 0;
}
题目4：整数划分问题。给定整数
n
n
n，求有多少种划分方案。比如3有1+1+1、1+2和3这3种划分方案。
思路：它属于计数类DP。
（解法一）
状态定义，f[i][j]：从前i个数中选，总和为j的方案数。
考虑最后一次选法，状态转移，有，
不选第i个数，即f[i-1][j]。选1个第i个数，即f[i-1][j-i]。选2个第i个数，即f[i-1][j - 2 * i] ……选s个第i个数，即f[i-1][j - s * i]。
故，综合上述，f[i][j]状态转移为，
f[i][j] = f[i-1][j] + f[i-1][j-i] + f[i-1][j - 2 * i] + f[i-1][j - 3 * i] + ... + f[i-1][j - s * i]
考虑状态f[i][j-i]的状态转移，有
f[i][j-i] = f[i-1][j-i] + f[i-1][j - 2 * i] + f[i-1][j - 3 * i] + ... + f[i-1][j - s * i]
故f[i][j]的状态转移可以写成，
f[i][j] = f[i-1][j] + f[i][j-i]
初始化，f[0][0] = 1。
同时利用滚动数组优化，可以有如下C++代码，
#include
using namespace std;
const int N = 1010, mod = 1e9 + 7;
int n;
int f[N];
int main() {
cin >> 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;
}
}
cout << f[n] << endl;
return 0;
}
（解法二） 状态表示f[i][j]：总和是i，有j个数，的所有方案数。
f[i][j]的状态转移，有，
拆分出来的数的最小值是1，即·f[i-1][j-1]。拆分出来的数的最小值大于1，即f[i-j][j]。
f[i][j]的状态转移为，
f[i][j] = f[i-1][j-1] + f[i-j][j]
初始化，f[0][0] = 1。
最终答案，f[n][1] + f[n][2] + ... + f[n][n]。
C++代码如下，
#include
using namespace std;
const int N = 1010, mod = 1e9 + 7;
int n;
int f[N][N];
int main() {
cin >> 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 res = 0;
for (int j = 1; j <= n; ++j) res = (res + f[n][j]) % mod;
cout << res << endl;
return 0;
}
相关文章
发表评论