咨询网站公司建设计划书,巨鹿网站建设多少钱,wordpress简约免费主题,网站手机模板和pc模板要分开做title: 线性动态规划 date: 2023-05-12 08:49:10 categories:
Algorithm动态规划 tags:动态规划 编辑距离
题目描述
设 A A A 和 B B B 是两个字符串。我们要用最少的字符操作次数#xff0c;将字符串 A A A 转换为字符串 B B B。这里所说的字符操作共有三种#xff1…
title: 线性动态规划 date: 2023-05-12 08:49:10 categories:
Algorithm动态规划 tags:动态规划 编辑距离
题目描述
设 A A A 和 B B B 是两个字符串。我们要用最少的字符操作次数将字符串 A A A 转换为字符串 B B B。这里所说的字符操作共有三种
删除一个字符插入一个字符将一个字符改为另一个字符。 A , B A, B A,B 均只包含小写字母。
输入格式
第一行为字符串 A A A第二行为字符串 B B B字符串 A , B A, B A,B 的长度均小于 2000 2000 2000。
输出格式
只有一个正整数为最少字符操作次数。
样例 #1
样例输入 #1
sfdqxbw
gfdgw样例输出 #1
4提示
对于 100 % 100 \% 100% 的数据 1 ≤ ∣ A ∣ , ∣ B ∣ ≤ 2000 1 \le |A|, |B| \le 2000 1≤∣A∣,∣B∣≤2000。
思路
状态表示f[i][j]表示将A的1i变成B的1j的操作次数的最小值
状态计算三种操作方式如下 删除将A[i]删除后应该与B[1~j]相同说明A[1~(i-1)]B[1~j] 方程为f[i-1][j]1 插入在A[i]之后插入后与B[1~j]相同则说明A[1~i]B[1~j-1] 方程为f[i][j-1]1 替换将A[i]替换后A[1~i]B[1~j]分两种情况 第一种是A[i]B[j]已经相等了不需要替换f[i-1][j-1]第二种是不想等需要替换一次f[i-1][j-1]1
状态转移方程为上述三个取min
初始化的时候需要将
f[i][0]i表示删除i个字符与B相等f[0][i]i表示添加i个字符与B相等 或者这样考虑 f[i][j]表示将A的1i变成B的1j的操作次数的最小值 如果A[i]B[j]则f[i][j]f[i-1][j-1], 如果A[i]!B[j], 使用三种操作取最小值 修改将a[i]改为b[i], f[i-1][j-1]1插入在a[i]后面插入b[i],f[i][j-1]1删除将a[i]删除,f[i-1][j]1 代码
#include bits/stdc.h#define int long long
using namespace std;
const int N 2010;
int f[N][N];//将A 1-i变成 B 1-j的最小操作次数
string a, b;signed main() {
#ifndef ONLINE_JUDGEfreopen(test.in, r, stdin);freopen(test.out, w, stdout);
#endifcin a b;int n a.size(), m b.size();a a, b b;for (int i 1; i n; i) f[i][0] i;for (int i 1; i m; i) f[0][i] i;for (int i 1; i n; i) {for (int j 1; j m; j) {if (a[i] b[j]) f[i][j] f[i - 1][j - 1];else f[i][j] min(f[i-1][j-1], min(f[i-1][j],f[i][j-1]))1;}}cout f[n][m];return 0;
}899. 编辑距离 - AcWing
给定 n n n 个长度不超过 10 10 10 10 10 10 的字符串以及 m m m次询问每次询问给出一个字符串和一个操作次数上限。
对于每次询问请你求出给定的 n n n 个字符串中有多少个字符串可以在上限操作次数内经过操作变成询问给出的字符串。
每个对字符串进行的单个字符的插入、删除或替换算作一次操作。
输入格式
第一行包含两个整数 n n n 和 m m m。
接下来 n n n 行每行包含一个字符串表示给定的字符串。
再接下来 m m m 行每行包含一个字符串和一个整数表示一次询问。
字符串中只包含小写字母且长度均不超过 10 10 10 10 10 10。
输出格式
输出共 m m m 行每行输出一个整数作为结果表示一次询问中满足条件的字符串个数。
数据范围 1 ≤ n , m ≤ 1000 1 \le n, m \le 1000 1≤n,m≤1000 1 ≤ n , m ≤ 1000 1 \le n, m \le 1000 1≤n,m≤1000,
输入样例
3 2
abc
acd
bcd
ab 1
acbd 2输出样例
1
3思路
和上一题一样将dp封装为一个函数即可。暴力统计是否能够转换。
代码
#include bits/stdc.h#define int long long
using namespace std;
const int N 20;
int f[N][N];int edit(string a, string b) {int n a.size(), m b.size();a a, b b;for (int i 1; i n; i) f[i][0] i;for (int i 1; i m; i) f[0][i] i;for (int i 1; i n; i) {for (int j 1; j m; j) {if (a[i] b[j]) f[i][j] f[i - 1][j - 1];else f[i][j] min(f[i - 1][j - 1], min(f[i][j - 1], f[i - 1][j])) 1;}}return f[n][m];
}signed main() {
#ifndef ONLINE_JUDGEfreopen(test.in, r, stdin);freopen(test.out, w, stdout);
#endifint n, m;cin n m;vectorstring a(n 1);for (int i 1; i n; i) cin a[i];while (m--) {string s;int limit;cin s limit;int res 0;for (int i 1; i n; i) {if (edit(a[i], s) limit) res;}cout res endl;}return 0;
}[NOIP1999 普及组] 导弹拦截
题目描述
某国为了防御敌国的导弹袭击发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷虽然它的第一发炮弹能够到达任意的高度但是以后每一发炮弹都不能高于前一发的高度。某天雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段所以只有一套系统因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度计算这套系统最多能拦截多少导弹如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
输入格式
一行若干个整数中间由空格隔开。
输出格式
两行每行一个整数第一个数字表示这套系统最多能拦截多少导弹第二个数字表示如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
样例 #1
样例输入 #1
389 207 155 300 299 170 158 65样例输出 #1
6
2提示
对于前 50 % 50\% 50% 数据NOIP 原题数据满足导弹的个数不超过 1 0 4 10^4 104 个。该部分数据总分共 100 100 100 分。可使用 O ( n 2 ) \mathcal O(n^2) O(n2) 做法通过。 对于后 50 % 50\% 50% 的数据满足导弹的个数不超过 1 0 5 10^5 105 个。该部分数据总分也为 100 100 100 分。请使用 O ( n log n ) \mathcal O(n\log n) O(nlogn) 做法通过。
对于全部数据满足导弹的高度为正整数且不超过 5 × 1 0 4 5\times 10^4 5×104。
思路 (LIS贪心 O ( n 2 ) O(n^2) O(n2))
第一问是LIS问题
LIS 是 Longest ascending subsequence 的缩写
显然每套导弹拦截系统拦截导弹高度为步上升子序列也就是最长不上升子序列只需要求最长不上升子序列的长度就可以了
状态的计算
for (int j 0; j i; j) if (q[j] q[i]) { // 不高于, 可以等于 最长下降子序列不完全下降可以等于严格来说是不上升子序列f[i] max(f[i], f[j] 1);第二问是贪心问题
贪心思路
较大的数的末尾元素比较小的数作为末尾元素的子序列更好因为这样可以让这个子序列变得更长如果放了一个较小的数可能放的数就没有那么长了
贪心步骤 开一个数组q[]记录所有下降子序列末尾元素 遍历每一个数对于当前的这个数 q[]中所有的数都比这个数大那么我们就扩大q[]的长度并且把这个数放到q[]中刚开的地方q[]中存在比这个数小的数那么我们就把当前的这个数覆盖到找到的比这个数小的最大的数 每次将一个较小的数换成一个较大的数作为末尾元素存储到q[], 随着q[]的长度扩大, 也就表示此时新增x比所有末尾元素都大时; q[]随下标增大元素值也越大, 因此q[]是单调上升的数组
这题的思路和AcWing 896. 最长上升子序列 II 一样我们可以得出结论
求解至少需要多少个下降子序列的数目 和
求解至多含有多少个上升子序列的数目是一个对偶问题
注数组q[]是单调不减的
代码
#include iostream
#include algorithmusing namespace std;const int N 1010;
int n;
int q[N];
int f[N], g[N];int main() {while (cin q[n]) n;int res 0;for (int i 0; i n; i) {f[i] 1;for (int j 0; j i; j) {if (q[j] q[i]) { // 不高于, 可以等于 最长下降子序列f[i] max(f[i], f[j] 1);}}res max(res, f[i]);}cout res endl;int cnt 0;//当前子序列的个数for (int i 0; i n; i) {int k 0;//记录下从前往后找到的比当前的数q[i]小的最大的数while (k cnt g[k] q[i]) k;// 当前的序列结尾的数我们的数g[k] q[i];if (k cnt) cnt;//没有任何一个数是大于等于我们当前数的}cout cnt endl;return 0;
}
思路2( O ( n 2 ) O(n^2) O(n2))
可以把题目理解为
给定一个序列求至少包含多少个下降子序列数目
等价于
给定一个序列求至多包含多少个上升子序列数目
也就是将题目转换为求解最长上升子序列的长度。
代码
#include iostream
#include algorithm
using namespace std;const int N 1010;
int n;
int a[N], f[N];int main()
{// 第一问问题是求最长下降子序列的长度while(cin a[n])n;int res 0;for (int i 0; i n; i) {f[i] 1;for (int j 0; j i; j)if (a[i] a[j])f[i] max(f[i], f[j] 1);res max(res, f[i]);}// 第二问问题转化为求解最长上升子序列的长度int len 0;for (int i 0; i n; i) {f[i] 1;for (int j 0; j i; j) if (a[i] a[j])f[i] max(f[i], f[j] 1);len max(len, f[i]);}cout res endl;cout len endl;return 0;
}思路3(二分LIS O ( n l o g n ) O(nlogn) O(nlogn))
注意这里第一问需要倒着求最长上升子序列这里的上升可以相等因此使用的是upper_bound函数
代码
#include bits/stdc.h#define int long long
using namespace std;const int N 1e5 10;
int a[N];
int n 1;signed main() {
#ifndef ONLINE_JUDGEfreopen(test.in, r, stdin);freopen(test.out, w, stdout);
#endifwhile (cin a[n])n;n--;vectorint f;f.push_back(a[n]);for (int i n - 1; i 1; i--) {if (a[i] f.back()) f.push_back(a[i]);else {//找到第一个大于a[i]的数换成a[i]*std::upper_bound(f.begin(), f.end(), a[i]) a[i];}}cout f.size() endl;vectorint g;g.push_back(a[1]);for (int i 2; i n; i) {if (a[i] g.back())g.push_back(a[i]);else *std::lower_bound(g.begin(), g.end(), a[i]) a[i];}cout g.size() endl;return 0;
}187. 导弹防御系统
题目链接https://www.acwing.com/problem/content/189/
为了对抗附近恶意国家的威胁 R R R 国更新了他们的导弹防御系统。
一套防御系统的导弹拦截高度要么一直 严格单调 上升要么一直 严格单调 下降。
例如一套系统先后拦截了高度为 3 3 3 和高度为 4 4 4的两发导弹那么接下来该系统就只能拦截高度大于 4 4 4 的导弹。
给定即将袭来的一系列导弹的高度请你求出至少需要多少套防御系统就可以将它们全部击落。
输入格式
输入包含多组测试用例。
对于每个测试用例第一行包含整数 n n n表示来袭导弹数量。
第二行包含 n n n 个不同的整数表示每个导弹的高度。
当输入测试用例 n 0 n0 n0 时表示输入终止且该用例无需处理。
输出格式
对于每个测试用例输出一个占据一行的整数表示所需的防御系统数量。
数据范围 1 ≤ n ≤ 50 1 \le n \le 50 1≤n≤50
输入样例
5
3 5 2 4 1
0 输出样例
2样例解释
对于给出样例最少需要两套防御系统。
一套击落高度为 3 , 4 3,4 3,4 的导弹另一套击落高度为 5 , 2 , 1 5,2,1 5,2,1 的导弹。
思路DFS迭代加深剪枝贪心
用up[k]和down[k]记录第k套上升下降系统目前所拦截的最后一个导弹
dfs(u,v,t)意味着已有u个上升v个下降正在处理第t个数
代码
#include bits/stdc.h#define int long long
using namespace std;int n;
const int N 60;
int a[N];
int up[N], down[N];
int ans 0;/*** param u 当前第几个导弹* param s 上* param x 下*/
void dfs(int u, int s, int x) {if (s x ans) return;if (u n 1) {ans s x;return;}//将当前数放到上升子序列中int k 0;while (k s up[k] a[u]) k; //大于等于当前数int t up[k];up[k] a[u];if (k s) dfs(u 1, s, x);else dfs(u 1, s 1, x);up[k] t;//回溯//将当前数放到下降子序列中k 0;while (k x down[k] a[u]) k;//小于等于当前数t down[k];down[k] a[u];if (k x) dfs(u 1, s, x);else dfs(u 1, s, x 1);down[k] t;
}void solve() {for (int i 1; i n; i) cin a[i];ans n;dfs(1, 0, 0);cout ans endl;
}signed main() {
#ifndef ONLINE_JUDGEfreopen(test.in, r, stdin);freopen(test.out, w, stdout);
#endifwhile (cin n, n) {solve();}return 0;
}AcWing 272. 最长公共上升子序列
题目链接https://www.acwing.com/problem/content/274/
熊大妈的奶牛在小沐沐的熏陶下开始研究信息题目。
小沐沐先让奶牛研究了最长上升子序列再让他们研究了最长公共子序列现在又让他们研究最长公共上升子序列了。
小沐沐说对于两个数列 A 和 B 如果它们都包含一段位置不一定连续的数且数值是严格递增的那么称这一段数是两个数列的公共上升子序列而所有的公共上升子序列中最长的就是最长公共上升子序列了。
奶牛半懂不懂小沐沐要你来告诉奶牛什么是最长公共上升子序列。
不过只要告诉奶牛它的长度就可以了。
数列 A 和 B 的长度均不超过 3000 。
输入格式
第一行包含一个整数 N N N表示数列 A B AB AB 的长度。
第二行包含 N N N 个整数表示数列 A A A。
第三行包含 N N N 个整数表示数列 B B B。
输出格式
输出一个整数表示最长公共上升子序列的长度。
数据范围 1 ≤ N ≤ 3000 1 \le N \le 3000 1≤N≤3000,序列中的数字均不超过 2 31 − 1 2^{31}-1 231−1。
输入样例
4
2 2 1 3
2 1 2 3输出样例
2思路
动态规划 状态表示f[i][j]代表所有a[1 ~ i]和b[1 ~ j]中以b[j]结尾的公共上升子序列的集合的子序列长度的最大值。 状态计算首先依据公共子序列中是否包含a[i]将f[i][j]所代表的集合划分成两个不重不漏的子集 不包含a[i]的子集最大值是f[i - 1][j]包含a[i]的子集将这个子集继续划分依据是子序列的倒数第二个元素在b[]中是哪个数 子序列只包含b[j]一个数长度是1子序列的倒数第二个数是b[1]的集合最大长度是f[i - 1][1] 1…子序列的倒数第二个数是b[j - 1]的集合最大长度是f[i - 1][j - 1] 1
代码
#include bits/stdc.h#define int long long
using namespace std;const int N 3010;
int f[N][N];
int a[N], b[N];
int n;signed main() {
#ifndef ONLINE_JUDGEfreopen(test.in, r, stdin);freopen(test.out, w, stdout);
#endifcin n;for (int i 1; i n; i) cin a[i];for (int i 1; i n; i) cin b[i];for (int i 1; i n; i) {for (int j 1; j n; j) {if (a[i] ! b[j]) f[i][j] f[i - 1][j];else {int mx 0;for (int k 1; k j; k) {if (b[k] b[j]) mx max(mx, f[i - 1][k]);}f[i][j] mx 1;}}}int res 0;for (int i 1; i n; i) res max(res, f[n][i]);cout res endl;return 0;
}优化使用define int long long 会内存超限
开一个变量maxn记录下子序列的倒数第二个元素在b[]中是哪个数的最大值防止每次都去求一次最大值。
代码
#include bits/stdc.husing namespace std;const int N 3010;
int f[N][N];
int a[N], b[N];
int n;int main() {
#ifndef ONLINE_JUDGEfreopen(test.in, r, stdin);freopen(test.out, w, stdout);
#endifcin n;for (int i 1; i n; i) cin a[i];for (int i 1; i n; i) cin b[i];for (int i 1; i n; i) {int mx 0;for (int j 1; j n; j) {if (a[i] ! b[j]) f[i][j] f[i - 1][j];else f[i][j] max(f[i][j], mx 1);if (a[i] b[j]) mx max(mx, f[i - 1][j] );}}int res 0;for (int i 1; i n; i) res max(res, f[n][i]);cout res endl;return 0;
}
