zoj 3747 uva 10328

zoj3747 链接
更多此题参考可以看这个博客
更多dp参考可以看这里
题意: 给n个士兵排队，每个士兵三种G、R、P可选，求至少有m个连续G士兵，最多有k个连续R士兵的排列的种数。

1.先把至少问题转为至多问题。
2.那么问题转化成：[至多n个连续G士兵+至多k个连续R士兵]-[至多m-1个连续G士兵]的情况

我们给定u,v，令：
dp[i][0] 第i个为G，至多u个连续G，至多v个连续R的个数。
dp[i][1] 第i个为R，至多u个连续G，至多v个连续R的个数。
dp[i][2] 第i个为P，至多u个连续G，至多v个连续R的个数。

记 sum = dp[i-1][0]+dp[i-1][1]+dp[i-1][2]
第i个为P时，不会对连续的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]。

最后一个问题。如何初始化边界？观察出现减号的部分，由于出现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的情况，数量是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个连续G v个连续R的个数
// 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 链接