uva 10069 - Distinct Subsequences(大数相加+DP)

发布时间：2020-12-14 03:59:40 所属栏目：大数据来源：网络整理

导读：1、http://uva.onlinejudge.org/index.php?option=com_onlinejudgeItemid=8page=show_problemproblem=1010 2、数据好大，longlong也不对，用大数相加 dp[i][j]表示b的前i个字符在a的前j个字符中出现的次数状态转移方程; if(b[i-1]==a[j-1])//如果b的第i个字

1、http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1010

2、数据好大，longlong也不对，用大数相加

dp[i][j]表示b的前i个字符在a的前j个字符中出现的次数

状态转移方程;

if(b[i-1]==a[j-1])//如果b的第i个字符和a的第j个字符相同，那么dp[i][j]=dp[i][j-1]+dp[i-1][j-1]

else

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

题目大意;

给定两个序列a,b,求出a中有多少个b序列，只要顺序相同即可，不必要连续

题目；

Problem E

Distinct Subsequences

Input:?standard input

Output:?standard output

A subsequence of a given sequence is just the given sequence with some elements (possibly none) left out. Formally,given a sequence?X?=x₁x₂…x_m,another sequence?Z?=?z₁z₂…z_k?is a subsequence of?X?if there exists a strictly increasing sequence?<i₁,?i₂,…,?i_k>?of indices of?Xsuch that for all?j?= 1,2,?k,we have?x_i_j?=?z_j. For example,?Z?=?bcdb?is a subsequence of?X?=?abcbdab?with corresponding index sequence<?2,3,5,7?>.

In this problem your job is to write a program that counts the number of occurrences of?Z?in?X?as a subsequence such that each has a distinct index sequence.

Input

The first line of the input contains an integer?N?indicating the number of test cases to follow.

The first line of each test case contains a string?X,composed entirely of lowercase alphabetic characters and having length no greater than 10,000. The second line contains another string?Z?having length no greater than 100 and also composed of only lowercase alphabetic characters. Be assured that neither?Z?nor any prefix or suffix of?Z?will have more than 10¹⁰⁰?distinct occurrences in?X?as a subsequence.

Output

For each test case in the input output the number of distinct occurrences of?Z?in?X?as a subsequence. Output for each input set must be on a separate line.

Sample Input

2
babgbag
bag
rabbbit
rabbit

Sample Output

5
3

____________________________________________________________________________________
Rezaul Alam Chowdhury

4、AC代码：

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
char a[10005];
char b[105];
char dp[105][10005][105];
void add(char *c,char *a,char *b)
{
    int la=strlen(a);
    int lb=strlen(b);
    int lc=max(la,lb);
    memset(c,(lc+2)*sizeof(c[0]));
    for(int i=la-1,j=lc;i>=0;i--,j--)
    c[j]+=a[i]-'0';
    for(int i=lb-1,j--)
    c[j]+=b[i]-'0';
    for(int i=lc;i>0;c[i]+='0',i--)
    {
        if(c[i]>9)
        {
            c[i]-=10;
            c[i-1]++;
        }
    }
    if(!c[0])
    {
        for(int i=0;i<lc;i++)
        c[i]=c[i+1];
        c[lc]=0;
    }
    else
    c[0]='1';
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%s%s",a,b);
        int la=strlen(a);
        int lb=strlen(b);
        for(int i=0;i<=la;i++)
        strcpy(dp[0][i],"1");
        for(int i=1;i<=lb;i++)
        {
            for(int j=i;j<=la;j++)
            {
                if(b[i-1]==a[j-1])
                add(dp[i][j],dp[i-1][j-1],dp[i][j-1]);
                else
                strcpy(dp[i][j],dp[i][j-1]);
            }
        }
        printf("%sn",dp[lb][la]);
    }
    return 0;
}

超时代码：（思路对，加上大数相加即可）

#include<stdio.h>
#include<string.h>
#define N 10005
char a[N];
char b[105];
int dp[105][N];//dp[i][j]表示子串的前i个字符在母串的前j个字符中出现的次数
int main()
{
    int t;
    scanf("%d",b);
        int la=strlen(a);
        int lb=strlen(b);
        memset(dp,sizeof(dp));
        for(int i=0;i<=la;i++)
        dp[0][i]=1;
        for(int i=1;i<=lb;i++)
        {
             for(int j=i;j<=la;j++)
             {
                 if(a[j-1]==b[i-1])
                 dp[i][j]=dp[i-1][j-1]+dp[i][j-1];
                 else
                 dp[i][j]=dp[i][j-1];
             }
        }
        printf("%dn",dp[lb][la]);
    }
    return 0;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!