Concerts (跳跃DP）

借鉴：https://blog.csdn.net/passer__/article/details/80135477

因为考虑到这种会往后跳跃形成不连序的情况，采取从后往前的状态转移

#include
#include
#include
#include 
using namespace std;
#define mod 1000000007
char str1[350];
char str2[100005];
int val[30];
int dp[100005][305];   //dp[i][j]表示第i天到第n天满足第j场比赛到第k场比赛的种类数//因为可以直接跳到很后面，所以从后往前开始转移
int main()
{int n,k;int i,j;scanf("%d%d",&k,&n);for(i=1;i<=26;i++)scanf("%d",&val[i]);scanf("%s",str1+1);//k  需要比较的串scanf("%s",str2+1);//n  母串//大串从最后一位枚举//小串也从最后一位枚举for(i=n;i>=1;i--)//枚举最大的那个串{for(j=k;j>=1;j--)//枚举比较的串{dp[i][j]=dp[i+1][j];          //这个初始化 没取当前点的操作，那就保持之前的这一状态if(j==k&&str1[j]==str2[i])   //这种情况只是下一种情况的特殊情况。{dp[i][j]+=1%mod;       dp[i][j]%=mod;}else if(i+val[str2[i]-'A'+1]+1<=n&&str1[j]==str2[i])  //dp{ dp[i][j]+=dp[i+val[str2[i]-'A'+1]+1][j+1]%mod;  //取了这个点，当前这样加就没什么问题dp[i][j]%=mod;}}}printf("%d\n",dp[1][1]);return 0;
}

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