subsequence 1(dp)

男娘i 2021-11-10 05:06 223阅读 0赞

题目链接：  
[https://ac.nowcoder.com/acm/contest/885/G?&headNav=acm][https_ac.nowcoder.com_acm_contest_885_G_headNav_acm]

1，我们可以利用组合数求出长度大于str2的个数。  
2，剩下的就是长度相同时的个数了。  
我们可以定义一个dp状态。  
dp\[i\]\[j\] 表示str1前i位和str2前j位完全匹配的个数。  
那么很明显的递推式了。  
首先不管当前str1\[i\] 和str2\[j\]的大小如何。dp\[i\]\[j\] 一定是等于dp\[i- 1\]\[j\]的。  
因为str1的前i- 1个字符和str2的前j个字符完全匹配的个数为dp\[i-1\]\[j\]。  
所以dp\[i\]\[j\] = dp\[i-1\]\[j\]。  
然后考虑str1\[i\]与str2\[j\]的大小情况。  
dp\[i\]\[j\] = dp\[i\]\[j\] + dp\[i -1\]\[j - 1\] (str1\[i\] == str2\[j\])  
if(str1\[i\] > str2\[j\])  
那么我们就可以用组合数来求解这个了。  
同时注意爆int

#include"stdio.h"
    #include"string.h"
    #include"algorithm"
    using namespace std;
    #define mod 998244353
    typedef long long ll;
    int n,m,T;
    char str1[3010],str2[3010];
    int c[3010][3010];
    int dp[3010][3010];
    
    int main()
    {
        c[0][0] = 1;
        for(int i = 1; i <= 3000; i ++)
             {
                c[i][0] = 1; c[i][i] = 1;
                 for(int j = 1; j < i; j ++)
                 {
                     c[i][j] = c[i - 1][j - 1] + c[i - 1][j];
                     c[i][j] %= mod;
                 }
             }
        scanf("%d",&T);
        while(T --)
        {
            scanf("%d%d",&n,&m);
            scanf("%s%s",str1 + 1,str2 + 1);
           
            int len1 = strlen(str1 + 1);
            int len2 = strlen(str2 + 1);
            ll sum = 0;
            for(int i = 0; i <= len1; i ++)
                dp[i][0] = 1;
            for(int i = 1; i <= len1; i ++)
            {
                for(int j = 1; j <= min(len2,i); j ++)
                {
                    dp[i][j] = dp[i - 1][j];
                    if(str1[i] == str2[j])
                        dp[i][j] = (dp[i][j] + (ll)dp[i - 1][j - 1]) % mod;
                    if(str1[i] > str2[j])//前j-1个字符完全匹配的个数乘上，后面的组合数。
                        sum = (sum + (ll)dp[i - 1][j -1] * c[len1 - i][len2 - j]) % mod;
                }
            }
            for(int i = 1; i <= len1 - len2; i ++)
            {
                if(str1[i] == '0') continue;
                for(int j = len2; j <= len1; j ++)
                    sum = (sum + c[len1 - i][j]) % mod;
            }
            printf("%lld\n",sum);
        }
    }

[https_ac.nowcoder.com_acm_contest_885_G_headNav_acm]: https://ac.nowcoder.com/acm/contest/885/G?&headNav=acm