20172018-acmicpc-southeastern-european-regional-programming-contest-seerc-2017-en A

题意就是给一个字母序列a，以及一个另外一个字母序列b，你需要b中找到字母序列a，并且要求对于在b中的字母序列a，每个单词都需要满足相应的距离

其实很简单，我们利用DP[i][j]代表a已经匹配i个位置，当前是在b串的j位置，这样我们很容易写出转移方程

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

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

第一个式子的意思是第 i 个位置匹配成功，是由第 i - 1匹配成功，并且减去a[i-1]所需要的时间，转移而来。

第二个式子是我们为了得到前面能满足的状态，需要把前面的状态保存起来。

#include<iostream>

#include<string.h>

#include<algorithm>

#include<stdio.h>

#define LL long long

const int maxx = 1e5+;

const int MOD =1e9+;

using namespace std;

int dp[][maxx];

int k,n;

int word[maxx];

char b[maxx];

char a[];

int main(){

  while(~scanf("%d%d",&k,&n)){

     for (int i=;i<=;i++){

          scanf("%d",&word[i]);

     }

     scanf("%s",a+);

     scanf("%s",b+);

     for (int i=;i<=n;i++){

        if (b[i]==a[]){

            dp[][i]=;

        }

     }

     for (int i=;i<=k;i++){

        for (int j=;j<=n;j++){

           if (a[i]==b[j]){

              int t=a[i-]-'A'+;

              if (j-word[t]->=)

              dp[i][j]=(dp[i][j]+dp[i-][j-word[t]-])%MOD;

           }

           dp[i][j]=(dp[i][j]+dp[i][j-])%MOD;

        }

     }

     LL ans=;

     printf("%d\n",dp[k][n]);

  }

  return ;

}

/*

2 10

1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

AB

ABBBBABBBB

*/

巴特西

20172018-acmicpc-southeastern-european-regional-programming-contest-seerc-2017-en A - Concerts

最新文章

热门文章