现在的位置: 首页 > 综合 > 正文

NYOJ 336 子序列

2017年07月15日 ⁄ 综合 ⁄ 共 904字 ⁄ 字号 评论关闭

http://acm.nyist.net/JudgeOnline/problem.php?pid=336

动态转移方程。。。。。。

首先我们把dp  开成二维的数组,dp[ i ] [ j ] 表示,a 串中以 第 i 个字符结尾,b 串中以第 j 个字符结尾, a 串包含 b 串的组数。

假设 a[ i ] == b [ j ] 

1、 如果包含 b 串 的a  串  含有 a [ i ] ,则dp[i][j] = dp[i-1][j-1], 原因是两个串中都以相同的字母结尾,则结尾字母就无所谓整个串了

2、如果包含 b 串的 a 串不含有a [ i ] ,则 dp[i][j] = dp[i-1][j-1], 原因是a 串中包含 b 串的子串 不包含 a [i] ,a [i] 就无所谓 a 的子串了。

3、由上面两种情况可以看到,第一位 都是i - 1, 所以我们每次运算的时候,对于第一维 只需要 上次的结果即可,第一维就不需要保存,但是也要注意不能被覆盖,因为 j > j - 1,

       所以我们进行递推的时候应该右后往前,这一点和0-1 背包由二维变一维很相似。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
int dp[100010];
string a,b;
int main()
{
    int n,i,j;
    cin>>n;
    while(n--)
    {
        cin>>a>>b;
        memset(dp,0,sizeof(dp));
        dp[0] = 1;
        int len_a = a.size(), len_b = b.size();
        if(len_a < len_b) cout<<0<<endl;
        else if(len_a == len_b)
        {
            //cout<<"****"<<endl;
            if(a==b) cout<<1<<endl;
            else cout<<0<<endl;
        }
        else
        {
            for(i = 0; i < len_a; i++)
            for(j = len_b-1; j >= 0; j--)
            {
                if(j > i) continue;
                if(a[i] == b[j])
                dp[j+1] = (dp[j+1] + dp[j]) %10003;
            }
            cout<<dp[len_b]<<endl;
        }

    }
    return 0;
}

抱歉!评论已关闭.