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

谁借莪１个温暖的怀抱￠ 2023-10-11 09:10 132阅读 0赞

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

显然从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[0][0]=1;
        for(int i=1;i<=3000;i++){
            C[i][0]=1;
            for(int j=1;j<=i;j++)
                C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
        }
    }
    
    void reserve(char s[]){
        int len=strlen(s);
        int i=0,j=len-1;
        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+1);
            scanf("%s",t+1);
            if(m>n){puts("0");continue;}
                    
            for(int i=0;i<=n;i++)
                for(int j=0;j<=m;j++)
                    dp[i][j]=0;
                        
            reserve(s+1);
            reserve(t+1);
            for(int i=1;i<=n;i++){
                //dp[i][0]=1;
                for(int j=1;j<=m&&j<=i;j++){
                    dp[i][j]=dp[i-1][j];//不选第i位 
                    if(s[i]>t[j])
                        dp[i][j]=(dp[i][j]+C[i-1][j-1])%mod;
                    if(s[i]==t[j])
                        dp[i][j]=(dp[i][j]+dp[i-1][j-1])%mod;
                }
            }
            
            ll ans=dp[n][m];
            
            reserve(s+1);
            for(int i=1;i<=n;i++)if(s[i]!='0'){
                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=3005,MOD=998244353;
     
    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+1,b+1);
        int ans=0;
        for (int i=1;i<=n;i++)
            if (a[i]!='0')
                for (int j=m;j<=n-i;j++)
                    (ans+=C[n-i][j])%=MOD;
        for (int i=0;i<=n;i++)
            for (int j=0;j<=m;j++)
                dp[i][j]=0;
        dp[0][0]=1;
        for (int i=1;i<=n;i++)
        {
            dp[i][0]=1;
            for (int j=1;j<=m;j++)
            {
                dp[i][j]=dp[i-1][j];
                if (a[i]==b[j])
                    (dp[i][j]+=dp[i-1][j-1])%=MOD;
                else if (a[i]>b[j])
                    ans=(ans+(LL)dp[i-1][j-1]*C[n-i][m-j])%MOD;
            }
        }
        printf("%d\n",ans);
    }
     
    int main()
    {
        #ifdef local
            freopen("read.txt","r",stdin);
        #endif
        for (int i=0;i<=3000;i++)
        {
            C[i][0]=1;
            for (int j=1;j<=i;j++)
                C[i][j]=(C[i-1][j-1]+C[i-1][j])%MOD;
        }
        int T;
        scanf("%d",&T);
        while (T--) solve();
        return 0;
    }

转载于:https://www.cnblogs.com/zsben991126/p/11285036.html