字符串dp——牛客多校第五场G

比赛的时候脑瘫了没想出来。。打多校以来最自闭的一场

显然从s中选择大于m个数组成的数必然比t大，所以只要dp求出从s中选择m个数大于t的方案数

官方题解是反着往前推，想了下反着推的确简单，因为高位的数优先级高，如果高位满足条件，那么低位只要用组合数求一下就行

#include<bits/stdc++.h>

using namespace std;

#define maxn 3005

#define ll long long

#define mod 998244353

int n,m;

char s[maxn],t[maxn];

ll dp[maxn][maxn];//dp[i][j]表示后面i个字符中取j个，比t大的方案数

ll C[maxn][maxn];

void init(){

    C[][]=;

    for(int i=;i<=;i++){

        C[i][]=;

        for(int j=;j<=i;j++)

            C[i][j]=(C[i-][j]+C[i-][j-])%mod;

    }

}

void reserve(char s[]){

    int len=strlen(s);

    int i=,j=len-;

    while(i<j){

        swap(s[i],s[j]);

        ++i,--j;

    }

}

int main(){

    int T;cin>>T;

    init();

    while(T--){

        cin>>n>>m;

        scanf("%s",s+);

        scanf("%s",t+);

        if(m>n){puts("");continue;}

        for(int i=;i<=n;i++)

            for(int j=;j<=m;j++)

                dp[i][j]=;

        reserve(s+);

        reserve(t+);

        for(int i=;i<=n;i++){

            //dp[i][0]=1;

            for(int j=;j<=m&&j<=i;j++){

                dp[i][j]=dp[i-][j];//不选第i位

                if(s[i]>t[j])

                    dp[i][j]=(dp[i][j]+C[i-][j-])%mod;

                if(s[i]==t[j])

                    dp[i][j]=(dp[i][j]+dp[i-][j-])%mod;

            }

        }

        ll ans=dp[n][m];

        reserve(s+);

        for(int i=;i<=n;i++)if(s[i]!=''){

            for(int j=m;j<=n-i;j++)

                ans=(ans+C[n-i][j])%mod;

        }

        cout<<ans<<'\n';

    }

}

然后是正着往后推，其实难度也不大，只不过状态表示为dp[i][j]为s中前i个取j个，和t取前j个相等的情况，然后转移过程中更新ans即可

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int MAXN=,MOD=;

int C[MAXN][MAXN],dp[MAXN][MAXN];

char a[MAXN],b[MAXN];

void solve()

{

    int n,m;

    scanf("%d%d%s%s",&n,&m,a+,b+);

    int ans=;

    for (int i=;i<=n;i++)

        if (a[i]!='')

            for (int j=m;j<=n-i;j++)

                (ans+=C[n-i][j])%=MOD;

    for (int i=;i<=n;i++)

        for (int j=;j<=m;j++)

            dp[i][j]=;

    dp[][]=;

    for (int i=;i<=n;i++)

    {

        dp[i][]=;

        for (int j=;j<=m;j++)

        {

            dp[i][j]=dp[i-][j];

            if (a[i]==b[j])

                (dp[i][j]+=dp[i-][j-])%=MOD;

            else if (a[i]>b[j])

                ans=(ans+(LL)dp[i-][j-]*C[n-i][m-j])%MOD;

        }

    }

    printf("%d\n",ans);

}

int main()

{

    #ifdef local

        freopen("read.txt","r",stdin);

    #endif

    for (int i=;i<=;i++)

    {

        C[i][]=;

        for (int j=;j<=i;j++)

            C[i][j]=(C[i-][j-]+C[i-][j])%MOD;

    }

    int T;

    scanf("%d",&T);

    while (T--) solve();

    return ;

}

巴特西

字符串dp——牛客多校第五场G

最新文章

热门文章