• 备战蓝桥杯 Day9（最长公共子序列LCS模型）

    多序列dp

    1265：【例9.9】最长公共子序列

    【题目描述】

    一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说，若给定序列X=�=<�1,�2,…,��>，则另一序列Z＝�＝<�1，�2，…，��>是X的子序列是指存在一个严格递增的下标序列<�1,�2,…,��>,使得对于所有j=1,2,…,k有：

      Xij=Zj���=��

    例如，序列Z=是序列X=的子序列,相应的递增下标序列为<2,3,5,7>。给定两个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。例如，若X＝和Y＝，则序列是X和Y的一个公共子序列,序列 也是X和Y的一个公共子序列。而且，后者是X和Y的一个最长公共子序列．因为X和Y没有长度大于4的公共子序列。

    给定两个序列X＝�＝<�1，�2，…，��>和Y=�=<�1,�2…．��>．要求找出X和Y的一个最长公共子序列。

    【输入】

    共有两行。每行为一个由大写字母构成的长度不超过1000的字符串，表示序列X和Y。

    【输出】

    第一行为一个非负整数。表示所求得的最长公共子序列的长度。若不存在公共子序列．则输出文件仅有一行输出一个整数0。

    【输入样例】

    ABCBDAB
BDCABA

    【输出样例】

    4

    【提示】

    最长公共子串（Longest Common Substirng）和最长公共子序列（Longest Common Subsequence，LCS）的区别为：子串是串的一个连续的部分，子序列则是从不改变序列的顺序，而从序列中去掉任意的元素而获得新的序列；也就是说，子串中字符的位置必须是连续的，子序列则可以不必连续。字符串长度小于等于1000。

    思路：
    状态 dp[i][j] s1的前i个字符和s2的前j个字符构成的最长公共子序列的长度
    状态转移方程:
        if(s1[i]==s2[j]) dp[i][j]=dp[i-1][j-1]+1;
        else dp[i][j]=max(dp[i][j-1],dp[i-1][j])

    1. #include
    2. using namespace std;
    3. #include 
    4. const int N=1e3+10;
    5. int dp[N][N];
    6. int main()
    7. {
    8.     string s1, s2; cin >> s1 >> s2;
    9.     int n = s1.size(), m = s2.size();//先计算不加空格的长度
    10.     s1 = ' '+s1; s2 = ' ' + s2;
    11.     //边界 dp[i][0]=dp[0][j]=0;//不需置
    12.     for (int i = 1; i <= n; i++)
    13.     {
    14.         for (int j =1; j <=m; j++)
    15.         {
    16.             if (s1[i] == s2[j])
    17.                 dp[i][j] = dp[i - 1][j - 1] + 1;
    18.             else
    19.                 dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
    20.         }
    21.     }
    22.     cout << dp[n][m];
    23.     return 0;
    24.  }

     

    1276：【例9.20】编辑距离

    【题目描述】

    设A和B是两个字符串。我们要用最少的字符操作次数，将字符串A转换为字符串B。这里所说的字符操作共有三种：

    1、删除一个字符；

    2、插入一个字符；

    3、将一个字符改为另一个字符。

    对任意的两个字符串A和B，计算出将字符串A变换为字符串B所用的最少字符操作次数。

    【输入】

    第一行为字符串A；第二行为字符串B；字符串A和B的长度均小于2000。

    【输出】

    只有一个正整数，为最少字符操作次数。

    【输入样例】

    sfdqxbw
gfdgw

    【输出样例】

    4

    思路：
    多序列dp-编辑距离Edit-Distance
    1.状态  dp[i][j] s1的前i个字符变为s2的前j个字符所需的最小操作数（即最短编辑距离）
    2.状态转移方程 
            if(s1[i]==s2[j]) dp[i][j]=dp[i-1][j-1]
            else dp[i][j]=min{dp[i-1][j]删除,dp[i][j-1]添加, dp[i - 1][j - 1]直接修改} + 1消耗一次操作数

    1. #include
    2. using namespace std;
    3. const int N = 2e3 + 10;
    4. int dp[N][N];
    5. int main() {
    6. 	//边界   dp[i][0]=i    dp[0][j]=j
    7. 	string s1, s2;
    8.     cin >> s1 >> s2;
    9.     int n = s1.size(), m = s2.size();
    10.     s1 = ' ' + s1;  s2 = ' ' + s2;//下标从1开始
    11.  
    12.     //边界
    13.     for (int i = 1; i <= n; i++) dp[i][0] = i;
    14.     for (int j = 1; j <= m; j++) dp[0][j] = j;
    15.  
    16. 	for (int i = 1; i <= n; i++) {
    17.         for (int j = 1; j <= m; j++) {
    18.             if (s1[i] == s2[j]) dp[i][j] = dp[i - 1][j - 1];
    19.             else dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
    20.         }
    21.     }
    22.     cout << dp[n][m] << endl;
    23. 	return 0;
    24. }

    1286：怪盗基德的滑翔翼

    【题目描述】

    怪盗基德是一个充满传奇色彩的怪盗，专门以珠宝为目标的超级盗窃犯。而他最为突出的地方，就是他每次都能逃脱中村警部的重重围堵，而这也很大程度上是多亏了他随身携带的便于操作的滑翔翼。

    有一天，怪盗基德像往常一样偷走了一颗珍贵的钻石，不料却被柯南小朋友识破了伪装，而他的滑翔翼的动力装置也被柯南踢出的足球破坏了。不得已，怪盗基德只能操作受损的滑翔翼逃脱。

    假设城市中一共有N幢建筑排成一条线，每幢建筑的高度各不相同。初始时，怪盗基德可以在任何一幢建筑的顶端。他可以选择一个方向逃跑，但是不能中途改变方向（因为中森警部会在后面追击）。因为滑翔翼动力装置受损，他只能往下滑行（即：只能从较高的建筑滑翔到较低的建筑）。他希望尽可能多地经过不同建筑的顶部，这样可以减缓下降时的冲击力，减少受伤的可能性。请问，他最多可以经过多少幢不同建筑的顶部(包含初始时的建筑)？

    【输入】

    输入数据第一行是一个整数K(K<100)�(�<100)，代表有K�组测试数据。

    每组测试数据包含两行：第一行是一个整数N(N<100)�(�<100)，代表有N�幢建筑。第二行包含N�个不同的整数，每一个对应一幢建筑的高度h(0

    【输出】

    对于每一组测试数据，输出一行，包含一个整数，代表怪盗基德最多可以经过的建筑数量。

    【输入样例】

    3
8
300 207 155 299 298 170 158 65
8
65 158 170 298 299 155 207 300
10
2 1 3 4 5 6 7 8 9 10

    【输出样例】

    6
6
9

    思路：
    状态 dp[i] 以第i个元素为结尾的最长上升子序列
    状态转移方程:if(a[j]

    最后求最长上升子序列和最长下降子序列的最大值

    1. #include
    2. using namespace std;
    3. #include 
    4. const int N=1e4+10;
    5. int dp_u[N],dp_d[N],a[N];
    6. int main()
    7. {
    8.     int k; cin >> k;
    9.     while (k--)
    10.     {
    11. 		int n; cin >> n;
    12. 		memset(dp_u,0,sizeof dp_u);
    13. 		memset(dp_d,0,sizeof dp_d);
    14. 		memset(a,0,sizeof a);
    15. 		for (int i = 1; i <= n; i++)
    16. 		{
    17. 			cin >> a[i];
    18. 			//边界
    19. 			dp_u[i]=dp_d[i]= 1;
    20. 		}
    21. 		for (int i = n; i >=1; i--)
    22. 		{
    23. 			for(int j=i+1;j<=n;j++)
    24. 			if (a[j] < a[i])
    25. 				dp_d[i] = max(dp_d[i], dp_d[j] + 1);
    26. 		}
    27. 		for (int i = 1; i <=n; i++)
    28. 		{
    29. 			for(int j=1;j
    30. 			if (a[j] < a[i])
    31. 				dp_u[i] = max(dp_u[i], dp_u[j] + 1);
    32. 		}
    33. 		int mx = 1;
    34. 		for (int i = 1; i <= n; i++)
    35. 			mx = max(max(mx,dp_d[i]),dp_u[i]);
    36. 		cout << mx << endl;
    37.     }
    38.     return 0;
    39.  }

     

    1297：公共子序列

    【题目描述】

    我们称序列Z=�=<�1,�2,...,��>是序列X=�=<�1,�2,...,��>的子序列当且仅当存在严格上升的序列<�1,�2,...,��>，使得对j=1,2,...,k,有xij=zj���=��。比如Z= 是X=的子序列。

    现在给出两个序列X和Y，你的任务是找到X和Y的最大公共子序列，也就是说要找到一个最长的序列Z，使得Z既是X的子序列也是Y的子序列。

    【输入】

    输入包括多组测试数据。每组数据包括一行，给出两个长度不超过200的字符串，表示两个序列。两个字符串之间由若干个空格隔开。

    【输出】

    对每组输入数据，输出一行，给出两个序列的最大公共子序列的长度。

    【输入样例】

    abcfbc abfcab
programming contest 
abcd mnp

    【输出样例】

    4
2
0
    1. #include 
    2. #include
    3. using namespace std;
    4. const int N=2e2+10;
    5. int dp[N][N];
    6. int main()
    7. {
    8. 	string s1, s2;
    9.     while (cin>>s1>>s2)
    10.     {
    11. 		memset(dp,0,sizeof dp);
    12.         int n = s1.length(), m = s2.length();
    13.         s1 = ' ' + s1; s2 = ' ' + s2;
    14.         for (int i = 1; i <= n; i++)
    15.         {
    16.             for (int j = 1; j <= m; j++)
    17.             {
    18.                 if (s1[i] == s2[j])
    19.                     dp[i][j] = dp[i - 1][j - 1] + 1;
    20.                 else
    21.                     dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
    22.             }
    23.         }
    24.         cout << dp[n][m]<
    25.     }
    26.     return 0;
    27.  }

     

    1298：计算字符串距离

    【题目描述】

    对于两个不同的字符串，我们有一套操作方法来把他们变得相同，具体方法为：    

    修改一个字符（如把“a”替换为“b”）;

    删除一个字符（如把“traveling”变为“travelng”）。

    比如对于“abcdefg”和“abcdef”两个字符串来说，我们认为可以通过增加/减少一个“g”的方式来达到目的。无论增加还是减少“g”，我们都仅仅需要一次操作。我们把这个操作所需要的次数定义为两个字符串的距离。

    给定任意两个字符串，写出一个算法来计算出他们的距离。

    【输入】

    第一行有一个整数n。表示测试数据的组数。

    接下来共n行，每行两个字符串，用空格隔开，表示要计算距离的两个字符串。

    字符串长度不超过1000。

    【输出】

    针对每一组测试数据输出一个整数，值为两个字符串的距离。

    【输入样例】

    3
abcdefg  abcdef
ab ab
mnklj jlknm

    【输出样例】

    1
0
4
    1. #include 
    2. #include
    3. using namespace std;
    4. const int N=1e3+10;
    5. int dp[N][N];
    6. int main()
    7. {
    8.     int k; cin >> k;
    9. 	string s1, s2;
    10.     while (k--)
    11.     {
    12.         cin >> s1; cin >> s2;
    13. 		memset(dp,0,sizeof dp);
    14.         int n = s1.length(), m = s2.length();
    15.         s1 = ' ' + s1; s2 = ' ' + s2;
    16.         for (int i = 1; i <= n; i++)
    17.             dp[i][0] = i;
    18.         for (int j = 1; j <= m; j++)
    19.             dp[0][j] = j;
    20.         for (int i = 1; i <= n; i++)
    21.         {
    22.             for (int j = 1; j <= m; j++)
    23.             {
    24.                 if (s1[i] == s2[j])
    25.                     dp[i][j] = dp[i - 1][j - 1];
    26.                 else
    27.                     dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]),dp[i-1][j-1])+1;
    28.             }
    29.         }
    30.         cout << dp[n][m]<
    31.     }
    32.     return 0;
    33.  }

     

     

  • 相关阅读:
    参照DefenseGrid在Unity中实现合理的塔防寻路机制
    【JavaEE】JavaScript webAPI的基本知识
    C语言字符串查找函数和错误信息报告函数（strstr、strtok，strerror）
    Java 第二阶段提升编程能力【泛型】
    开发环境安装---Visual Studio Code
    Swift-day 2
    理论学习-ARM-内核
    彭友会出品，绝对精品！史上最强DMBOK学习资料出炉！
    集合——List接口：关于ArrayList、LinkedList和Vector的区别
    2022 CCPC 桂林 (22-10-30) B
  • 原文地址：https://blog.csdn.net/m0_68987050/article/details/136189849