出题人题解 | #背单词#

原题解链接：https://ac.nowcoder.com/discuss/150263

入门动态规划:

时间复杂度$O(N+(A+B))O(N+(A+B))$

$dp[5000][2][50]dp[5000]\; [2]\; [50]$

第一个维度表示当前处理到第几个位置也就是DP的阶段,第二个维度表示重复的是元音还是辅音，第三个维度表示重复的次数。

对于每一个阶段。考虑4种转移。

上一个是元音当前状态也是元音的转移。

上一个是辅音当前状态是元音的转移。

上一个是元音当前状态是辅音的转移。

上一个是辅音当前状态也是辅音的转移。

转移方程:

$dp[i][0][j]+=dp[i-1][0][j-1]\ast 5dp[i][0][j]+\; =dp[i-1][0][j-1]*5$;

$dp[i][0][1]+=dp[i-1][1]\ast 5dp[i][0][1]+\; =dp[i-\; 1][1]*5$;

$dp[i][1][1]+=dp[i-1][0][j]\ast 21dp[i][1][1]+\; =dp[i-1][0][j]*21$;

$dp[i][1][j]+=dp[i-1][1][j-1]\ast 21dp[i][1][j]+\; =dp[i-1][1][j-1]*21$;

#include<bits/stdc++.h>
using namespace std;
long long  dp[5050][2][60];
const long long mod=(long long)1e9+7LL;
int n,a,b;
long long dfs(int pos,int pre,int cnt,int flag)
{
	long long sum=0;
	if(pos==-1)
	{
		return flag;
	}
	if(flag&&dp[pos][pre][cnt]!=-1)return dp[pos][pre][cnt];
	if(flag==0)
	{
		sum=(sum+dfs(pos-1,-1,-1,0))%mod;
		sum=(sum+dfs(pos-1,0,1,1)*5)%mod;
		sum=(sum+dfs(pos-1,1,1,1)*21)%mod;
	}
	else if(pre==0)
	{
		if(cnt<a)
			sum=(sum+dfs(pos-1,0,cnt+1,1)*5)%mod;
		sum=(sum+dfs(pos-1,1,1,1)*21)%mod;
	}
	else
	{
		if(cnt<b)
			sum=(sum+dfs(pos-1,1,cnt+1,1)*21)%mod;
		sum=(sum+dfs(pos-1,0,1,1)*5)%mod;
	}
	if(flag)dp[pos][pre][cnt]=sum;
	return sum;
}

int main()
{
	/*freopen("e:\\1.in","r",stdin);
	freopen("e:\\1.out","w",stdout);*/
	int t;
	cin>>t;
	
	while(t--)
	{
		memset(dp,-1,sizeof(dp));
		scanf("%d%d%d",&n,&a,&b);
		printf("%lld\n",dfs(n-1,-1,-1,0));
	}
}
/*
int main()
{
	freopen("e:\\1.in","w",stdout);
	int n=50;
	cout<<n<<endl;
	for(int i=0;i<n;i++)
	{
		cout<<rand()%5000+1<<" "<<rand()%50+1<<" "<<rand()%50+1<<endl;
	}
}*/
/*
500
 200 30 40
 4500 15 25
 150 3 4
 1700 21 1
 1900 1 42



 200 30 40
360495170
 4500 15 25
545588643
 150 3 4
579059385
 1700 21 1
784374553
 1900 1 42

832513636


 500
 200 30 40
360495170
 4500 15 25
336444490
 150 3 4
441384413
 1700 21 1
764797355
 1900 1 42

420898572
 */