2017-2018 ACM-ICPC Southeastern European(SEERC 2017) A concerts

题目大意：字符串只由A~Z组成，给定s字符串长度k(k<=300)，p字符串长度是n(<=1e5)，再给定字母A~Z匹配成功后需要间隔的次数a[27]，再给出字符串s, p。求s匹配p的方案数

dp[i][j]:匹配到i位置时已经匹配了j个的方案数。
(1) s[j]==p[i]：dp[i][j] = dp[i-1][j] + dp[i-a[id]-1][j-1];
(2) s[j]!=p[i]：dp[i][j] = dp[i-1][j]；
喜提新技能:列出所有情况，找规律得转移方程

#include 
#include using namespace std;
typedef long long ll;
const int mod = 1e9+7;
const int N = 1e5+10;
const int K = 310;
int dp[N][K];
char s[K], p[N];
int a[27];
int k, n;int main()
{scanf("%d %d", &k, &n);for(int i = 0; i < 26; ++i)scanf("%d", &a[i]);scanf("%s", s+1);scanf("%s", p+1);memset(dp, 0, sizeof(dp));for(int i = 1; i <= n; ++i){dp[i][1] = dp[i-1][1];if(s[1]==p[i]) ++dp[i][1];//printf("%d\n", sum[i][1]);}for(int i = 1; i <= n; ++i)for(int j = 2; j <= k; ++j){dp[i][j] = dp[i-1][j];if(s[j]==p[i]){int id = s[j-1]-'A';if(i-a[id]-1<1) continue;dp[i][j] = (dp[i][j]+dp[i-a[id]-1][j-1])%mod;}}printf("%d\n", dp[n][k]);return 0;
}

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