ErikTse Runtime

  • 首页 / Home
  • | 算法学习 / Algorithm
    • 所有 / All
    • 简单 / Easy
    • 中等 / Medium
    • 困难 / Hard
  • | 技术分享 / Technology
    • 所有 / All
    • 网络技术 / NetWork
    • 资源共享 / Resource
    • 项目实践 / Event
  • ETOJ在线评测系统
Keep Going.
温故而知新.
  1. 首页
  2. 算法学习
  3. 中等
  4. 正文

2022ICPC亚洲网络选拔赛L.LCS-like Problem(DP + 字符串)

2022年9月20日 257点热度 1人点赞 0条评论

可以在PTA补题。

题目大意 / Problem

给定两个字符串s和t,求一个s的子串s'使得s'和t的最大公共子串长度不超过1,问s'的最大长度。

子串可以不连续。

思路 / Thought

先把字符转换成[0, 25]的数字方便处理。

根据题意判断应该是个DP。由于是一个和位置和字符有关的dp,状态可以设为\(dp[i][j]\),表示到s的第i个位置为止,最后一个敏感字符(定义为存在于t中的字符)为j的最大合法s'长度。

还需要预先处理一个ban数组,ban[i][j]表示在s'中字符i后面不能接j,这样会导致s'与t的公共子串有至少两个字符相同。这个数组需要从后往前处理,记录一下哪些字符在从后往前的过程中已经出现,并且记录下来更新ban数组。

从前往后遍历s数组,到第i位时有两种情况,第一种是s[i]没在t中出现过,也就是这个字符加入到s'中不会对公共子串长度造成影响。第二种情况是s[i]在t中出现过,就只有ban[j][s[i]]为假的情况才能将状态dp[i - 1][j]转移到dp[i][s[i]]。

在转移时,前一个状态为:到s的i - 1位为止,以j作为敏感字符结尾的字符串最大长度。

当前状态为到s的i位为止,以j或s[i]作为敏感字符结尾的字符串最大长度。

最后只需要输出dp[n][i](0 <= i < 26)的最大值就好了。

代码 / Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 5e5 + 9;
int n, m;
bitset<30> vis, ban[30];//vis[i]表示i在t中出现过,标记为敏感字符 
int dp[maxn][30];
char s[maxn], t[maxn];

signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	
	cin >> s + 1;
	cin >> t + 1;
	n = strlen(s + 1), m = strlen(t + 1);
	for(int i = 1;i <= n; ++ i)s[i] -= 'a';
	for(int i = 1;i <= m; ++ i)t[i] -= 'a';
	
	for(int i = m;i >= 1; -- i)
	{
		for(int j = 0;j < 26; ++ j)if(vis[j])ban[t[i]][j] = true;
		vis[t[i]] = true;
	}
	
	for(int i = 1;i <= n; ++ i)
	{
		for(int j = 0;j < 26; ++ j)
		{
			dp[i][j] = max(dp[i][j], dp[i - 1][j]);//延续性 
			
			if(!vis[s[i]])//从j转移过来敏感字符依然是j
				dp[i][j] = max(dp[i][j], dp[i - 1][j] + 1);
			else if(!ban[j][s[i]])//敏感字符是s[i] 
				dp[i][s[i]] = max(dp[i][s[i]], dp[i - 1][j] + 1);	 
		}
	}
	
	int ans = 0;
	for(int i = 0;i < 26; ++ i)ans = max(ans, dp[n][i]);
	cout << ans << '\n';
	
	return 0;
}
本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: C++ DP icpc 思维 算法竞赛
最后更新:2022年9月20日

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

点赞
< 上一篇
下一篇 >

文章评论

取消回复

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

文章目录
  • 题目大意 / Problem
  • 思路 / Thought
  • 代码 / Code

友情链接 | 站点地图

COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

Theme Kratos | Hosted In TENCENT CLOUD

赣ICP备2022001555号-1

赣公网安备 36092402000057号