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

  题意就是给一个字母序列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
#include<string.h>
#include
#include
#define LL long long
const int maxx = 1e5+6;
const int MOD =1e9+7;
using namespace std;
int dp[305][maxx];
int k,n;
int word[maxx];
char b[maxx];
char a[305];
int main(){while(~scanf("%d%d",&k,&n)){for (int i=1;i<=26;i++){scanf("%d",&word[i]);}scanf("%s",a+1);scanf("%s",b+1);for (int i=1;i<=n;i++){if (b[i]==a[1]){dp[1][i]=1;}}for (int i=1;i<=k;i++){for (int j=1;j<=n;j++){if (a[i]==b[j]){int t=a[i-1]-'A'+1;if (j-word[t]-1>=1)dp[i][j]=(dp[i][j]+dp[i-1][j-word[t]-1])%MOD;}  dp[i][j]=(dp[i][j]+dp[i][j-1])%MOD;}}LL ans=0;printf("%d\n",dp[k][n]);}return 0;
}
/*
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
*/

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！