【简单DP】Children’s Queue

向右看齐 2024-03-26 16:40 66阅读 0赞

**哈哈，独立做出来了，不错**

**感觉这种暴力DP还是很好做的**

[Problem - 1297 (hdu.edu.cn)][Problem - 1297 _hdu.edu.cn]

题意：

![43293c2d2b066406f62084d4045d0d74.png][]

思路：

写了这么多DP，我认识到DP的状态设计是最难的

首先看阶段，就是第i个人

然后影响决策的因素就是，女生不能单独存在

因此需要知道前一个人是男生还是女生

因此设

dp\[i\]\[0\]\[0\]为前i个人，第i-1个和第i个都是女生

dp\[i\]\[0\]\[1\]为前i个人，第i-1个是女生，第i个是男生

dp\[i\]\[1\]\[0\]为前i个人，第i-1个是男生，第i个是女生

dp\[i\]\[1\]\[1\]为前i个人，第i-1个人和第i个人都是男生

这样就很好转移了

注意：这道题需要预处理DP数组，否则会超时

Code：

#include <bits/stdc++.h>
    using namespace std;
    const int mxn=1e6+10;
    const int Inf=0x3f3f3f3f;
    const int mod=1e9+7;
    int n;
    int dp[mxn][2][2];
    void solve(){
        while(cin>>n) cout<<((dp[n][0][0]+dp[n][0][1])%mod+dp[n][1][1])%mod<<'\n';
    }
    void init(int n){
        for(int i=1;i<=n;i++) dp[i][0][0]=dp[i][0][1]=dp[i][1][0]=dp[i][1][1]=0;
        dp[1][1][0]=1;
        dp[1][1][1]=1;
        for(int i=2;i<=n;i++){
            dp[i][0][0]=(dp[i-1][1][0]+dp[i-1][0][0])%mod;
            dp[i][0][1]=dp[i-1][0][0]%mod;
            dp[i][1][1]=(dp[i-1][0][1]+dp[i-1][1][1])%mod;
            if(i==n) dp[i][1][0]=0;
            else dp[i][1][0]=(dp[i-1][0][1]+dp[i-1][1][1])%mod;
        }
    }
    int main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        init(mxn);
        while(__--)solve();return 0;
    }

[Problem - 1297 _hdu.edu.cn]: https://acm.hdu.edu.cn/showproblem.php?pid=1297
[43293c2d2b066406f62084d4045d0d74.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/385c3f3999e5444c99faf61b5b860e5a.png