2019牛客暑期多校训练营(第五场)G - subsequeue 1 (一题我真的不会的题)


layout: post

title: 2019牛客暑期多校训练营(第五场)G - subsequeue 1 (一题我真的不会的题)

author: "luowentaoaa"

catalog: true

tags:

mathjax: true

- ACM-ICPC


题意

给你两个由数字组成的字符串\(S\),\(T\) 长度为\(1e3\),问你S中有多少个子序列的值大于字符串T;

思路

首先在比赛的时候一眼确定是\(N^2\) 复杂度的DP,但是想了两三个小时却没想到怎么转移,各种构造\(dp[i][j]\)的含义。可是无功而返。

比赛结束后发现大家都用到了组合数。发现大家这题都用分两类来讨论做题。这时候才焕然大悟。

原来比T大的字符串可以分成两类根本不用瞎几把转移。

于是这题的解法很快就想到了,如果是大于的情况,那么只要第一个字符不是0,那么后面的几个字符串就随便取就行了。

大于的结束了接下来就是相等的情况。如果相等 那么肯定要考虑是从\(S\)串的哪个作为起点来构造子序列。并且这个S串的起点,的下一个点从哪里转移。这些都是可以DP的。于是我们基本的状态确定了,我们首先要确定目前构造到S串的哪个位置了。同时这个位置对于着T串的哪个位置,这样我们就可以开始转移。

#include<bits/stdc++.h>
using namespace std;
const int maxn=4e3+50;
typedef long long ll;
const ll mod=998244353;
ll dp[maxn][maxn];
ll C[maxn][maxn];
void add(ll &a,ll b){
a+=b;
if(a>=mod)a-=mod;
}
char s[maxn],t[maxn];
int main(){
std::ios::sync_with_stdio(false);
int T;
C[0][0]=1;
for(int i=1;i<=3000;i++){
for(int j=0;j<=i;j++){
if(j==0||j==i)C[i][j]=1;
else add(C[i][j],C[i-1][j-1]+C[i-1][j]);
}
}
cin>>T;
while(T--){
int n,m;
cin>>n>>m;
cin>>s+1>>t+1;
for(int i=0;i<=n+10;i++){
for(int j=0;j<=m+10;j++)dp[i][j]=0;
}
ll ans=0;
for(int i=1;i<=n;i++){
if(s[i]=='0')continue;
for(int j=m;j<=n;j++){
add(ans,C[n-i][j]);
}
}
///dp[i][j]= 从后往前到当前S串第j的字符位置匹配到T串的第I个字符并且大于的个数
for(int i=m;i;i--){
for(int j=n;j;j--){
dp[j][i]=dp[j+1][i]; ///因为包括了没有第j个字符的情况,所以如果第j+1个字符符合条件也可以
if(t[i]==s[j])add(dp[j][i],dp[j+1][i+1]);
/// 如果两个字符相同 那么答案就是少取这第J个字符同时还大于的数量
if(t[i]<s[j])add(dp[j][i],C[n-j][m-i]);
///如果大于 那么答案就是后面的几个随便取几个就行了。
}
}
cout<<(ans+dp[1][1])%mod<<endl;
}
return 0;
}
上一篇:转载--------Python中:self和__init__的含义 + 为何要有self和__init__


下一篇:Loadrunner中web_find和web_reg_find函数的使用与区别