http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5170
参考:
http://blog.csdn.net/cc_again/article/details/24841249
UPDATE:
第二次做的感受,说下这道题为什么用递推。对于这种排序,且连续至多的问题,每个点放什么受到之前那个点是什么的影响,也就是说这个点的情况可以由前面那个点的情况推出来
题目意思:
给n个士兵排队,每个士兵三种G、R、P可选,求至少有m个连续G士兵,最多有k个连续R士兵的排列的种数。
一个最多,一个最少很难判断。可以转化成两个最多。
至少有m个 = 取值 m~n = {最多有n个} - {最多有m-1个}
因为是求总情况个数,第n个的情况可以从第n-1个的情况推出,所以可以用递推。
然后就是状态方程:
第i个的情况,至少有u个G,k个R
dp[i][0] 表示 G
dp[i][1] 表示 R
dp[i][2] 表示 P
当第i个为P时 前面没有任何限制条件, dp[i][2] = dp[i-1][0] + dp[i-1][1] + dp[i-1][2]
当第i个为G时
若 i<=u 没有任何限制, dp[i][0] = dp[i-1][0] + dp[i-1][1] + dp[i-1][2]
若 i=u+1 需要减去前u个都是G的情况,dp[i][0] = dp[i-1][0] + dp[i-1][1] + dp[i-1][2]-1
若i>u+1 需要减去(i-1)~(i-u)个连续G的情况,dp[i][0] = dp[i-1][0] + dp[i-1][1] + dp[i-1][2]-dp[i-u-1][1]-dp[i-u-1][2]
当第i个为R时 同G
#include <iostream>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <stack>
using namespace std; #define MEM(a,b) memset(a,b,sizeof(a))
#define pf printf
#define sf scanf
#define debug printf("!/m")
#define INF 1100000
#define MAX(a,b) a>b?a:b
#define blank pf("\n")
#define LL long long
#define M 1000000007 LL dp[INF][];
LL n,m,k,u,v; LL Cal()
{
dp[][] = ;//初始化时可以随意放一个,没有什么影响,因为后面已经把所有情况考虑进去
dp[][] = ;
dp[][] = ;
int i;
for(i = ;i<=n;i++)
{
LL sum = (dp[i-][] + dp[i-][] + dp[i-][])%M;
dp[i][]=sum;
if(i<=u)
dp[i][] = sum;
else if(i==u+)
dp[i][] = (sum-)%M;
else
dp[i][] = (sum - dp[i-u-][] - dp[i-u-][])%M; if(i<=v)
dp[i][] = sum;
else if(i==v+)
dp[i][] = (sum - )%M;
else
dp[i][] = (sum - dp[i-v-][] - dp[i-v-][])%M; }
return (dp[n][]+dp[n][]+dp[n][])%M;
} int main()
{
while(~sf("%lld%lld%lld",&n,&m,&k))
{
u = n;v = k;
LL ans = Cal();
u = m-;v = k;
ans = ((ans - Cal())%M+M)%M;
pf("%lld\n",ans);
} return ;
}