简单dp之递推(2)--ZOJ 3747

题目链接:

ZOj 3747

---

题意:

给n个士兵排队，每个士兵有三种类型G、R、P可选，求至少有m个连续G士兵，最多有k个连续R士兵的排列的种数。

---

题目输入输出:

Input

There are multiple test cases. For each case, there is a line containing 3 integers N (0 < N < 1000000), M (0 < M < 10000) and K (0 < K < 10000), separated by spaces.

Output

One line for each case, you should output the number of ways mod 1000000007.

Sample Input

3 2 2 Sample Output

5 Hint

Denote the Garrison, the Recon Corp and the Military Police as G, R and P. Reasonable arrangements are: GGG, GGR, GGP, RGG, PGG.

---

思路:

由于又是至多又是至少没办法处理，所以统一转换成至多，对于事件A={至多N个G士兵连续}，事件B={至多M-1个G士兵连续},那么A-B={连续人数在M到N中取值，即至少m个连续士兵}。统一之后， 设dp[i][j]表示前i个士兵，当第i个士兵是第j种兵（假设G：0，R：1，P：2）时，G至多连续u个、R至多连续v个的排列个数。

令sum=dp[i-1][0]+dp[i-1][1]+dp[i-1][2]；对于不作要求的P士兵，它可以由第i-1阶段的三种士兵任意转移：dp[i][2]=sum。

另：

对于G种兵 假设 i<=u 这时第i个位置可以随意放入GRP任意一种，即dp[i][0]=sum; 假设i==u+1时这时要排除1~u 全为G的情况 所以此时的dp[i][0]=sum-1; 假设i>u+1 时这时要排除i-u~i-1全为G的情况 这种状态即为i-u~i-1全为G时i-u-1为P或R的情况，即dp[i][0]=sum-dp[i-u-1][1]-dp[i-u-1][2];

对于R种兵，则与上述G种兵类似。

初始化时，对于第0个位置，整体为1即可，也可理解为对第0个位置放P，并没有什么影响。 dp[0][2]=1,dp[0][0]=dp[0][1]=0; （其实只需要dp[0][2]+dp[0][1]+dp[0][0]=0;即可）

这样，我们令u分别等于N和M-1，v等于K，进行两次递推，得到的结果相减即是答案。

---

代码:

#include <stdio.h> #include <algorithm> using namespace std; #define LL long long #define mod 1000000007 LL dp[1000009][3]; //G:0 R:1 P:2 LL N,M,K; LL fun(LL u,LL v) { int i,j; dp[0][1]=dp[0][0]=0; dp[0][2]=1; for(i=1;i<=N;i++) { LL sum=(dp[i-1][0]+dp[i-1][1]+dp[i-1][2])%mod; dp[i][2]=sum; if(i<=u)dp[i][0]=sum; else if(i==u+1)dp[i][0]=(sum-1)%mod; else dp[i][0]=(sum-dp[i-u-1][1]-dp[i-u-1][2])%mod; if(i<=v)dp[i][1]=sum; else if(i==v+1)dp[i][1]=(sum-1)%mod; else dp[i][1]=(sum-dp[i-v-1][0]-dp[i-v-1][2])%mod; } return (dp[N][0]+dp[N][1]+dp[N][2])%mod; } int main() { while(scanf("%lld%lld%lld",&N,&M,&K)!=EOF) { LL ans=fun(N,K); ans=((ans-fun(M-1,K))%mod+mod)%mod; //注意减法可能出现负数，这儿坑了好几次，取模的时候要特别处理一下。 printf("%lld\n",ans); } return 0; }