Problem G: 沉迷字符的WJJ (LCS)
字符 Problem LCS
2023-09-11 14:22:48 时间
Contest - 河南省多校连萌(四)
Problem G: 沉迷字符的WJJ
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 6 Solved: 5
SubmitWeb Board
Description
WJJ最近迷恋上了字符串,每次大家一起吃饭时他都会在大家面前炫耀一番新学的知识,于是
KKK和FFF决定难为一下WJJ。KKK和FFF分别写一个字符串s1和s2,要求WJJ也写一个字符串s3。
要求WJJ回答两个问题:
1、s1和s2都为s3的子序列并且使s3的长度最短
2、s3的组成方案有多少种?
Input
第一行输入一个t,表示t组数据
然后每组数据输入两个字符串,分别为s1,s2, 0<|s1|<=30, 0<|s2|<=30
Output
输出两个数分别为满足条件的s3的长度len1和方案数sum(sum小于2^63),输出占一行
Sample Input
3
ALKJ
SADIU
AAA
BBB
ABABAB
BABABA
Sample Output
8 20
6 20
7 2
HINT
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 char s1[45], s2[45]; 6 long long dp[45][45], sum[45][45]; 7 8 int main () 9 { 10 int t; 11 cin >> t; 12 while(t--) 13 { 14 cin >> s1+1 >> s2+1; 15 int m = strlen(s1+1); 16 int n = strlen(s2+1); 17 memset(sum, 0, sizeof(sum)); 18 for(int i = 0;i <= m;i++) dp[i][0] = i, sum[i][0] = 1;//初始化 19 for(int i = 0;i <= n;i++) dp[0][i] = i, sum[0][i] = 1; 20 for(int i = 1;i <= m;i++) 21 for(int j = 1;j <= n;j++) 22 { 23 if(s1[i] == s2[j]) 24 { 25 dp[i][j] = dp[i-1][j-1] + 1; 26 sum[i][j] = sum[i-1][j-1]; 27 } 28 else 29 { 30 dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 1; 31 if(dp[i][j-1] >= dp[i-1][j]) sum[i][j] += sum[i-1][j]; 32 if(dp[i-1][j] >= dp[i][j-1]) sum[i][j] += sum[i][j-1]; 33 } 34 } 35 printf("%lld %lld\n", dp[m][n], sum[m][n]); 36 } 37 return 0; 38 }
LCS的变形, dp[i][j]就是s1中前i个字符和s2中前j个字符可以得到的满足条件的长度
当s1[i] == s2[j]时 dp[i][j] = d[i-1][j-1] + 1
不相等时 dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 1 //在dp[i-1][j-1]的基础上加上s1或s2中的一个字符取其最短,然后再加一
sum[i][j]表示方案数
当s1[i] == s2[j]时 sum[i][j] = sum[i-1][j-1] //方案数不变
不相等时 如果dp[i][j-1] == dp[i-1][j], 那么两个方向都可以选择, 所以 sum[i][j] = sum[i-1][j] + sum[i][j-1]
如果dp[i][j-1] < dp[i-1][j] sum[i][j] = sum[i][j-1] //长度最短时的方案数
如果dp[i][j-1] > dp[i-1][j] sum[i][j] = sum[i-1][j]
感觉这种题如果真正明白了,动态规划的原理其实也没有那么难,这一题的关键主要是理解上面的那段题解。
相关文章
- list 序列号为字符json:字符串json序列化为list
- hdu 5284 wyh2000 and a string problem(没有算法,仅仅考思维,字符数组得开20万,不然太小了)
- shell 判断字符串最后一个字符
- SQL Server中的Replicate函数。循环字符次数,可用于多层分类
- java基础—IO流——将一些字符写入到指定硬盘上的目录中去:
- Delphi中获取不同编码下一个字符一段文字占用多少字节的方法
- 输入一行字符,分别统计出其中英文字母、空格、数字和其它字符的个数
- 关于以16进制打印字符型出现FFFF**的问题
- mysql取电话号码的后四位字符
- 字符设备驱动(实验一)——保姆级教程
- JS获取指定字符的前/后值
- 剑指offer解法汇总75-字符流中第一个不重复的字符
- 力扣解法汇总2423. 删除字符使频率相同
- sql server 小技巧(5) Sql server 获取指定字符后的所有字符 - 去掉指定字符前的所有字符
- 把字符串每隔四个字符使用“-”中横线分隔的方法
- Java检查字符串是否包含中文字符
- C++中字符数组与string的相互转换
- 字符数组和字符指针