【动态规划】subsequence 1

 

题目链接：https://ac.nowcoder.com/acm/contest/885/G

题意:

两个串，s  t，求s的所有子串中大于 t  的数目

题解：

　　dp[i][j] 表示 s的前i个，匹配 t 的前 j 个的种类数，

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

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

　　　　else

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

　　对于长度大于 t 的没有前导0的都符合，那么就看长度等于t的就可以了，

　　当匹配到 i， j 的时候，if(s[i] > t[j]) 那么该贡献为：

　　　　前面匹配j-1的种类数*后面随便选len2-j个，即当前的贡献就为dp[i - 1][j - 1] * C[len1 - i][len2 - j]。

 

---

 

 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3005;
const ll mod = 998244353 ;
char s[N],t[N];
ll C[N][N];
ll dp[N][N];
int main()
{
    //打表杨辉三角
    C[0][0] = 1 ;
    C[1][0] = C[1][1] = 1 ;
    for(int i=2;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] ;
            if(C[i][j]>=mod) C[i][j] -= mod ;
        }
    }

    int T,n,m;
    for( scanf("%d",&T) ; T ; T-- ){
        scanf("%d%d",&n,&m);
        scanf("%s%s",s+1,t+1);

        for(int i=0;i<=n;i++){
            dp[i][0] = 1 ;
        }
        //计算长度相同时，某一位置比t的位置大，对答案的贡献
        ll ans = 0 ;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=min(i,m);j++){
                dp[i][j] = dp[i-1][j] ;
                if( s[i] == t[j] ){
                    dp[i][j] = (dp[i][j] + dp[i-1][j-1]) % mod ;
                }
                else if( s[i] > t[j] ){
                    ans = (ans + (ll)dp[i-1][j-1] * C[n-i][m-j]) %mod ;
                }
            }
        }
        //计算长度大于t串长度时，对答案的贡献
        for(int i=1;i<=n;i++){
            if( s[i] =='0' ) continue ;
            for(int j=m;j<=n-i;j++){
                ans = (ans + C[n-i][j])%mod ;
            }
        }
        printf("%lld
",ans);
    }
    return 0;
}