zoj3747 鏈接
更多此題參考可以看這個博客
更多dp參考可以看這里
題意: 給n個士兵排隊，每個士兵三種G、R、P可選，求至少有m個連續(xù)G士兵，最多有k個連續(xù)R士兵的排列的種數(shù)。

1.先把至少問題轉為至多問題。
2.那么問題轉化成：[至多n個連續(xù)G士兵+至多k個連續(xù)R士兵]-[至多m-1個連續(xù)G士兵]的情況

我們給定u,v，令：
dp[i][0] 第i個為G，至多u個連續(xù)G，至多v個連續(xù)R的個數(shù)。
dp[i][1] 第i個為R，至多u個連續(xù)G，至多v個連續(xù)R的個數(shù)。
dp[i][2] 第i個為P，至多u個連續(xù)G，至多v個連續(xù)R的個數(shù)。

記 sum = dp[i-1][0]+dp[i-1][1]+dp[i-1][2]
第i個為P時，不會對連續(xù)的R和G產生影響，所以dp[i][2]=sum。
第i個為G時，若i<=u，那么無論如何不破壞限制。dp[i][1]=sum。
若i>u，那么要留意，要滿足至多u個G，在[i-u，i-1]這個位置里，不能都放G，要排除這種情況。這種情況有多少種?假設[i-u，i-1]都放G，那么改變的就是[1,i-u-1]這部分了，所以有dp[i-u-1][1]+dp[i-u-1][2]兩類。所以dp[i][1]=sum-dp[i-u-1][1]-dp[i-u-1][2]
同理，第i個為R時若i<v，dp[i][2]=sum。否則其=sum-dp[i-u-1][0]-dp[i-u-1][1]。

最后一個問題。如何初始化邊界？觀察出現(xiàn)減號的部分，由于出現(xiàn)i-1和i-u-1，而i∈[1,N]，所以要初始化dp[0]，最小幾時遇到dp[0]？在i=u+1或i=v+1的時候，此時的意思是，第u+1個置G/R，那么要去除的情況相當于[1,u]全是G/R的情況，數(shù)量是1，所以令dp[0][2]為1，其它兩個為0即可。
綜上所述:

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define ll long long
#define mst(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
const double eps = 1e-8, PI = acos(-1.0f);
const int inf = 0x3f3f3f3f, maxN = 1e6 + 5;
const int mod = 1e9 + 7;

ll N, M, K, u, v;
ll dp[maxN][5];
// dp[i][0] 第i個為G 至多:u個連續(xù)G v個連續(xù)R的個數(shù)
// dp[i][1] 第i個為R
// dp[i][2] 第i個為P

ll cal() {
    dp[0][0] = 0;
    dp[0][1] = 0;
    dp[0][2] = 1;

    rep(i, 1, N + 1) {
        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
            dp[i][0] = (sum - dp[i - u - 1][1] - dp[i - u - 1][2]) % mod;

        if (i <= v)
            dp[i][1] = sum;
        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)) {
        u = N, v = K;
        ll c1 = cal();

        u = M - 1, v = K;
        ll c2 = cal();
        printf("%lld\n", ((c1 - c2) % mod + mod) % mod);
    }
    return 0;
}

另外有一題相似的：
uva 10328 鏈接