dp递推 zoj 3747 Attack on Titans

╰+攻爆jí腚メ 2022-08-19 14:16 148阅读 0赞

题意：

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

分析：

不是很好想的一道题。但是想通之后也是可以很好理解的。

我们试着将一个至多一个至少都变成至多的情况，至多K个连续的R，至少M个连续的G，这时我们可以看成是至多n个连续的G减去至多m-1个G，那剩下的情况不就是至少M个连续G的情况了吗。

dp\[i\]\[0\] 表示的是当第i个士兵是R时的种数，此时至多u个连续G，至多v个连续R（u，v为常数）；

dp\[i\]\[1\] 表示的是当第i个士兵是G时的种数，此时至多u个连续G，至多v个连续R（u，v为常数）；

dp\[i\]\[2\] 表示的是当第i个士兵是P时的种数，此时至多u个连续G，至多v个连续R（u，v为常数）。

最终的结果是dp\[n\]\[0\]+dp\[n\]\[1\]+dp\[n\]\[2\] 。

递推关系为：

sum = dp\[i-1\]\[0\] + dp\[i-1\]\[1\] + dp\[i-1\]\[2\] ;

当第i个士兵是P时没有任何限制，所以这时候dp\[i\]\[2\] = sum 。

当第i个士兵是G的时候，当i<=u的时候，这时候没有超出限制，可以随便放，所以这时dp\[i\]\[1\] = sum ；

当i=u+1的时候，这时候要减去前u个士兵都是G的情况，所以这时dp\[i\]\[1\] = sum -1 ；

当i>u+1的时候，要减去i-u到i-1之间都是G的情况，这时i-1-u的位置可以放P或者R，所以dp\[i\]\[1\] = sum - dp\[i-u-1\]\[0\] - dp\[i-u-1\]\[2\]。

当第i个士兵是R的时候，情况同上。

#include <iostream>
    #include <cstdio>
    #include <cmath>
    #include <cstring>
    #include <algorithm>
    #include <queue>
    using namespace std;
    
    #define LL long long
    #define mod 1000000007
    int const maxn = 1100000;
    LL dp[maxn][3];
    //dp[i][0]表示的是第i个是R，dp[i][1]表示的是第i个是G，dp[i][2]表示的是第i个是P
    LL u,v,n,m,k;
    
    LL cal()
    {
        //memset(dp,0,sizeof(dp));
        dp[0][0] = 1 ; //初始化
        dp[0][1] = 0 ;
        dp[0][2] = 0 ;
        for(int i = 1 ; i <= n ; i++)
        {
            LL sum = (dp[i-1][0]+dp[i-1][1]+dp[i-1][2])%mod ;
            dp[i][2] = sum ;
            //第i个是P的时候没有限制条件
            if(i<=u) dp[i][1] = sum ;
            else if(i==u+1) dp[i][1] = (sum - 1 +mod)%mod ;
            else dp[i][1] = (sum - dp[i-u-1][0] - dp[i-u-1][2] + mod)%mod;
            //第i个是G的时候，有限制条件，但i小于等于u的时候随意放，当i==u+1的时候要减去前u个都是G
            //的情况，当i>u+1的时候，要减去i-u到i-1之间都是G的情况，这时i-1-u的位置可以放P或者R
            if(i<=v) dp[i][0] = sum ;
            else if(i==v+1) dp[i][0] = (sum - 1 + mod)%mod ;
            else dp[i][0] = (sum - dp[i-v-1][1] - dp[i-v-1][2] +mod)%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 ;
            //至多有u个连续的G，k个连续的R
            LL ans = cal();
    
            u = m-1 ;
            v = k ;
            ans = ((ans - cal())%mod + mod)%mod ;
            printf("%lld\n",ans);
        }
        return 0;
    }