FZU2126:消去游戏(DP)

#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;
}