PTA——L3-020 至多删三个字符 (30分)

2020-11-05

题目:

给定一个全部由小写英文字母组成的字符串,允许你至多删掉其中 3 个字符,结果可能有多少种不同的字符串?

输入格式:

输入在一行中给出全部由小写英文字母组成的、长度在区间 [4, 10​6​​] 内的字符串。

输出格式:

在一行中输出至多删掉其中 3 个字符后不同字符串的个数。

输入样例:

ababcc

输出样例:

25

提示:

删掉 0 个字符得到 "ababcc"。

删掉 1 个字符得到 "babcc", "aabcc", "abbcc", "abacc" 和 "ababc"。

删掉 2 个字符得到 "abcc", "bbcc", "bacc", "babc", "aacc", "aabc", "abbc", "abac" 和 "abab"。

删掉 3 个字符得到 "abc", "bcc", "acc", "bbc", "bac", "bab", "aac", "aab", "abb" 和 "aba"。

分析:

dp[i][j] 代表从前 i 个字符中删除 j 个字符的所有方案
属性:个数
对于第 i 个字符有两种情况删除或者不删除
便可以得到 dp[i][j]=dp[i-1][j]+dp[i-1][j-1];前者是不删除 后者是删除 很容易发现会有重复元素
例子假设一个字符串为 abstaba 很容易发现删除 ab 和删除 ba 得到字符串一样都是 absta
那么如何去考虑重复的个数呢?
因为最多删除 3 个字符假设对于第 i 个字符对其有影响的最多是 i-3 例如上式,重复的元素个数就是在这个范围内遇到的第一个与其相等的字符 因为我们先更新的 dp[][]方程所以会被计算两次,只需要将与其相同的字符前面的方案数删掉即可即 令 t 为 s[t]=s[i]那么重复元素就是 dp[t-1][j-(i-t)],j 为枚举的删除元素的个数

接下来的表格会很清晰的表达出来
image.png

#include<bits/stdc++.h>

using namespace std;

const int N=1e6+10;

typedef long long LL;

LL dp[N][4];

int main()
{
	string s;
	cin>>s;
	s=" "+s;
	int len=s.size();
	dp[0][0]=1;
	
	for(int i=1;i<len;i++) {
		for(int j=0;j<=3;j++) {
			dp[i][j]=dp[i-1][j];//不删第i个字符 
			if(j) dp[i][j]+=dp[i-1][j-1];//删第i个字符 
			for(int k=i-1;k>=1&&(i-k)<=j;k--) {
				if(s[i]==s[k]) {
					dp[i][j]-=dp[k-1][j-(i-k)];//减去重复计算的数目 
					break;
				}
			}	
		}
	}
	
	for(int i=1;i<len;i++) {
		for(int j=0;j<=3;j++) {
			cout<<dp[i][j]<<' ';
		}
		cout<<'\n';
	} 
	
	LL ans=0;
	for(int i=0;i<=3;i++)	
		ans+=dp[len-1][i];
		
	cout<<ans<<'\n';
	
	return 0;
	
}

标题:PTA——L3-020 至多删三个字符 (30分)
作者:xiaob0
地址:https://xiaobo.net.cn/articles/2020/11/05/1604585462663.html