題干：

winterzz1準備考4級了，現在winterzz1決定把世界上所有單詞都背一遍，winterzz1發現任意一個單詞最多有A個連續的元音，最多有B個連續的輔音。且單詞最長長度為N，winterzz1問你在滿打滿算的情況他需要背多少單詞？？？

輸入描述:

首先輸入一個T(T<=100)，表示有T組案例，每組案例依次輸入三個正整數N,A,B，N<=5000,A<=50,B<=50;

輸出描述:

輸出winterzz1最多需要背多少單詞，結果mod(10^9+7)

示例1

輸入

復制

2 2 2 2 500 20 30

輸出

復制

702 175540856

備注:

元音字母為a,e,i,o,u，其余21個字母均為輔音

解題報告：

? ?這題不算難其實。。。dp[i][j][k]就完事了。。。不過超時了10多次后發現是因為mod運算了太多次了，，把mod改成const就火速AC了、、、好氣啊、、不過可能是因為dp的姿勢不太正確，，應該可以先記憶下來然后快速冪直接解決一下。。

? 這題抽象出來的意思就是：長度為n的01串，其中連續1的個數不能超過x個，連續0的個數不能超過y個。給定n,x,y，問能構造出多少合法串。。然后再加強一下：對0和1，有兩個對應的權值，，這就變成這道題了。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #include<ctime> #define ll long long #define pb push_back #define pm make_pair #define fi first #define se second using namespace std; const int MAX = 2e5 + 5; ll dp[5005][2][55];//0代表元音，1代表輔音 const ll mod = 1e9+7; int n,a,b; int main() {int t;scanf("%d",&t);while(t--) {scanf("%d%d%d",&n,&a,&b);int up = max(a,b);for(int i = 0; i<=n; i++) {for(int j = 0; j<=50; j++) {dp[i][0][j]=dp[i][1][j]=0;//別只初始化到up，，因為有可能上次的up更大，所以沒有初始化完全。。。}}if(n == 1) {puts("26");continue;}dp[1][0][1]=5;dp[1][1][1]=21;for(int i = 2; i<=n; i++) {//更新元音的for(int j = 1; j<=min(i-1,b); j++) dp[i][0][1] = (dp[i][0][1] + dp[i-1][1][j]*5ll%mod)%mod;for(int j = 2; j<=min(i,a); j++) dp[i][0][j] += dp[i-1][0][j-1]*5%mod;//更新輔音的for(int j = 1; j<=min(i-1,a); j++) dp[i][1][1] = (dp[i][1][1]+dp[i-1][0][j]*21%mod)%mod;for(int j = 2; j<=min(i,b); j++) dp[i][1][j] += dp[i-1][1][j-1]*21%mod;}ll ans = 0;for(int i = 1; i<=n; i++) {for(int j = 1; j<=50; j++) {if(j <= a) ans = (ans + dp[i][0][j])%mod;if(j <= b) ans = (ans + dp[i][1][j])%mod;}}printf("%lld\n",ans);}return 0 ;} /* 2 2 2 2 500 20 30 */

還有一個10msAC的代碼，（以后再補一下吧、、）：

（這個代碼大概意思就是先dp[i][j]算出所有的，再減去連續a個元音的，或者連續b個輔音的，，也不算難想到啊其實，不知道比賽的時候在干什么。。唉可能還是自己苔菜了、、）

#include<bits/stdc++.h> using namespace std; using LL=unsigned long long; const int M=6e3+5; const int mo=1e9+7; LL dp[M][2],cnt[M]; LL qpow(LL a,LL b) {LL res=1;while(b>0){if(b&1)res=res*a%mo;b>>=1;a=a*a%mo;}return res; } int main() {int t;scanf("%d",&t);while(t--){int n,a,b;scanf("%d%d%d",&n,&a,&b);for(int i=1;i<=n;i++)dp[i][0]=dp[i][1]=0;dp[0][0]=dp[0][1]=1;dp[1][0]=5;dp[1][1]=21;cnt[1]=26;LL pa=qpow(5,a+1),pb=qpow(21,b+1),res=26;// cout<<pa<<"=="<<pb<<endl;for(int i=2;i<=n;i++){dp[i][0]=5*cnt[i-1]%mo;dp[i][1]=21*cnt[i-1]%mo;if(i>a)dp[i][0]=(dp[i][0]-dp[i-a-1][1]*pa%mo+mo)%mo;if(i>b)dp[i][1]=(dp[i][1]-dp[i-b-1][0]*pb%mo+mo)%mo;cnt[i]=(dp[i][0]+dp[i][1])%mo;res=(cnt[i]+res)%mo;}printf("%lld\n",res);}return 0; }

?

總結

以上是生活随笔為你收集整理的*【牛客 - 326B】背单词（线性dp）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。