题意
有N个小球排成了一排，每个小球可以被染成M种颜色之一，不能连续K个或者K个以上的小球颜色一样， 问一共有多少种不同的染色方法么？
分析
dp啊！！！可以解决一切问题2333
定义：dp[i][j]：表示第i个数与前面连续j个数相同（包括位置i）
转移：dp[i][j]：分析可知，可分为 j 是否为1，j为1时，说明可以选m-1中颜色，不为1时要和i-1相同
答案：对dp[n][1~k-1]求和即为答案
#include <bits/stdc++.h> #define ll long long using namespace std; const int maxn = 524300 ; const int maxm = 1e5 + 3; const ll mod = 1e9+7; ll n,m,k; ll dp[1005][1005]; int main() { scanf("%lld%lld%lld", &n, &m, &k); dp[1][1]=m; for(int i=2;i<=n;i++) { for(int j=1;j<k;j++) { dp[i][1]=(dp[i][1]+dp[i-1][j]*(m-1))%mod; } for(int j=2;j<k && j<=i;j++) { dp[i][j]=dp[i-1][j-1]; } } ll sum=0; for(int i=1;i<k;i++) sum+=1ll*dp[n][i],sum%=mod; printf("%lld\n", sum); return 0; }
原文：http://www.cnblogs.com/Superwalker/p/7993169.html
