删除子序列＜每日一题＞

题目：

题目链接 ：登录—专业IT笔试面试备考平台_牛客网

题目所求为s中能删除t的最大次数

其实是贪心的思想

思路1：对于s字符串中取最大的t字符串

我们可以用一个数组记录下t字符串中

每个字符出现的顺序

再遍历s数组

对于s数组中每个在t中有的字符

出现的次数进行统计

但是要注意设计限制条件

当遍历s时每次s的字符

统计出现的次数时要小于它在

t中的位置的前一个字符的数量

这样就可以达到对所有满足条件的结果进行统计

（原因：相当于按照t字符串的顺序进行统计）

思路2：假设我们在s字符串中最大能删除n次字符串

那么我们要怎么删才能达到删除n次字符串勒

答案是从第n次字符串开始删除

并且第n次字符后面所有的字符都可以删除(对次数无影响)

然后删除n-1次的字符串

然后依次往前删除

这样就可以保证能删除完n次所有的字符串

（原因：每次从后往前的删除就保证了

对前面满足条件的字符串不造成影响

依次的删除就能保证达到最大删除次数）

思路1代码详解：

#include
#include
using namespace std;
typedef long long ll;
#include
using namespace std;
int n, m;
int pos[30], ans[30];
string s, t;
int main()
{
	int ts;
	cin >> ts;
	while (ts--)
	{
		scanf("%d%d", &n, &m);
		memset(pos, -1, sizeof(pos));
		memset(ans, 0, sizeof(ans));//每次样例都需初始化数组
		cin >> s >> t;
		for (int i = 0; i < m; i++) pos[t[i] - 'a'] = i;//记录下t数组里面每个字符出现的顺序

		for (int i = 0; i < n; i++)
		{
			if (s[i] == t[0]) ans[0]++;//对于t的第一个字符出现的数量进行统计
			else
			{
				int step = pos[s[i] - 'a'];
				if (step!= -1 && ans[step] < ans[step - 1])
					ans[step]++;//代码关键！如果s中的该字符存在于t中，并且出现的次数小于该字符在t中的前一个字符。那么该次数可以加1
			}
		}
		printf("%dn", ans[m - 1]);//输出最后满足t顺序条件的字符串数量
	}
	return 0;
}

思路2代码（官方代码）：

#include 
typedef unsigned long long ull;
typedef long long ll;
#define inf 0x3f3f3f3f
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define nep(i, r, l) for (int i = r; i >= l; i--)
void sc(int &x) { scanf("%d", &x); }
void sc(int &x, int &y) { scanf("%d%d", &x, &y); }
void sc(int &x, int &y, int &z) { scanf("%d%d%d", &x, &y, &z); }
void sc(ll &x) { scanf("%lld", &x); }
void sc(ll &x, ll &y) { scanf("%lld%lld", &x, &y); }
void sc(ll &x, ll &y, ll &z) { scanf("%lld%lld%lld", &x, &y, &z); }
void sc(char *x) { scanf("%s", x); }
void sc(char *x, char *y) { scanf("%s%s", x, y); }
void sc(char *x, char *y, char *z) { scanf("%s%s%s", x, y, z); }
void out(int x) { printf("%dn", x); }
void out(ll x) { printf("%lldn", x); }
void out(int x, int y) { printf("%d %dn", x, y); }
void out(ll x, ll y) { printf("%lld %lldn", x, y); }
void out(int x, int y, int z) { printf("%d %d %dn", x, y, z); }
void out(ll x, ll y, ll z) { printf("%lld %lld %lldn", x, y, z); }
void ast(ll x,ll l,ll r){assert(x>=l&&x<=r);}
using namespace std;
const int N=1e6+5,mod=998244353;
int n,m;
char s[N],t[N];
int main()
{
  // freopen("1.in", "r",stdin);
  //   freopen("1.out", "w", stdout);
  int ts;sc(ts);ast(ts,1,10000);
  int sum=0;
  while(ts--)
  {
    scanf("%d%d",&n,&m);
    sc(s+1);sc(t+1);
    ast(n,1,1000000);ast(m,1,min(n,26));
    sum+=n;
    ast(sum,1,1000000);
    assert(strlen(s+1)==n);assert(strlen(t+1)==m);
    rep(i,1,n) ast(s[i],'a','z');
    rep(i,1,m) ast(t[i],'a','z');
    for(int i=1;i<=m;i++)
      for(int j=i+1;j<=m;j++) assert(t[i]!=t[j]);
    vectorvc[26];
    rep(i,1,n)
      vc[s[i]-'a'].emplace_back(i);
    int ans=0;
    while(true)
    {
      bool flag=true;
      int las=n+1;
      for(int i=m;i>=1;i--)
      {
        while(vc[t[i]-'a'].size()&&vc[t[i]-'a'].back()>=las) vc[t[i]-'a'].pop_back();
        if(vc[t[i]-'a'].empty()){flag=false;break;}
        las=vc[t[i]-'a'].back();
        vc[t[i]-'a'].pop_back();
      }
      if(!flag) break;
      ans++;
    }
    out(ans);
  }
}

 

PS:苟利国家生死以，岂因祸福避趋之！____林则徐《赴戍登程口占示家人·其二》