大家好，又见面了，我是全栈君，今天给大家准备了Idea注册码。
Problem Description
S近期在玩一种游戏。
这样的游戏的规则是一个一个地往一个栈里放有颜色的球，当栈顶连续k个球颜色同样时。这k个球立马同一时候消失。
如今S已经往栈里放了n个球，他想知道再放m个球，然后使得栈里的球都被消去的放法有多少种。两种放法不同是指存在放的第i个球这两种放法放的球的颜色不同。因为方法数可能非常多，将答案mod 1000000007。
Input
输入包括多组数据。输入数据的第一行为四个整数n,m,h,k(0<=n,m,h<=1000,2<=k<=1000)，表示已经放了n个球，有h种不同颜色的球，若栈顶出现连续k个球颜色同样则这k个球同一时候消失，问再放m个球。使得最后栈里的球都被消去的放法数。
第二行从左往右依次输入n个整数，范围为1到h,表示刚開始往栈里放的球的颜色，放入顺序与输入顺序同样，数据保证已经放入的n个球不会存在连续k个球颜色同样。答案对1000000007取余。
Output
输出一行一个整数M,表示对1000000007取余后的放法数。
Sample Input
3 6 3 3 1 2 20 6 2 3
Sample Output
98
dp[i][j]代表还须要放i个球，还有j个球须要消去的情况
#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
const int mod = 1000000007;
int n,m,h,k;
int cur,pre,tot;
long long dp[1005][1005];
int main()
{
int i,j;
while(~scanf("%d%d%d%d",&n,&m,&h,&k))
{
memset(dp,0,sizeof(dp));
pre = cur = tot = 0;
for(i = 0; i<n; i++)
{
scanf("%d",&cur);
if(cur != pre)//不等于前面，还须要k-1个球才干消去
tot+=k-1;
else//来一个相等的就减去1
tot--;
pre = cur;
}
dp[m][tot] = 1;//直接按如今所存在的数字消去的方法仅仅有一种
for(i = m; i>0; i--)
{
for(j = i; j>=0; j--)
{
if(i-1>=j+k-1)//假设末尾放一个与栈末尾的求不同的球，那么对应的情况要多加k-1个球
dp[i-1][j+k-1] = (dp[i-1][j+k-1]+dp[i][j]*(j?(h-1):h))%mod;
if(j-1<0)
break;
dp[i-1][j-1] = (dp[i-1][j-1]+dp[i][j])%mod;//依据前面能够知道，我在末尾放一个与栈尾同样的球，那么我还须要放的个数必定是减去1的
}
}
printf("%lld\n",dp[0][0]);
}
return 0;
}
版权声明：本文博客原创文章。博客，未经同意，不得转载。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/117257.html原文链接：https://javaforall.net
