Gym 101669A Concerts DP

题意： 给定n, k。26个数。给出两个串。第一个sk串为要得到的串，第二个串为母串。求在母串中可以匹配出多少种sk串。【要求：有些特定字母在选定之后要间隔几个才能选中下一个】。

答案%1e9+7;

很明显是DP， 比赛时我没有做出来。

其实这道题的模型也很显然是那种相邻两位关系的DP。。不过加入了要间隔的问题我就不会了。。。

做题还是要先简化模型， 先往自己学过的模型上靠。

dp[i][j] i表示母串中的位置， j表示子串（sk串）中的位置。

最外层循环确定在子串中的位置，内层循环跑出符合答案的情况，将答案赋给相同位。

#include 
#define ms(x) memset(x, 0, sizeof(x))
#define ll long long
using namespace std;
const int N = 1123;
const int mod = 1e9+7;
const int maxN = 100005, maxK = 310;
int dp[maxN][maxK];
int dis[30];
int n, k;
char sn[maxN], sk[maxK];
int main(){scanf("%d%d", &k,&n);for(int i=0;i<26;i++){scanf("%lld", &dis[i]);}scanf("%s",sk+1);scanf("%s",sn+1);ms(dp);dp[0][0] = 1;for(int tk=1;tk<=k;tk++){int index = 0;ll now  = 0;int cha = (tk==1)?0:dis[sk[tk-1]-'A'];for(int i=1;i<=n;i++){while(index+cha

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