codeforces (G) The Debut Album dp+滚动数组

太过爱你忘了你带给我的痛 2022-08-22 04:56 10阅读 0赞

[点击打开链接][Link 1]

题意: 找长度为n(n<=50000)的由1和2组成的字符串, 连续的1的个数不超过a(a<=300)个, 连续的2的个数不超过b(b<=300)个, 求满足题意的字符串的不同种类的数目.

分析:以前做过类似的题目, 用的是记忆化的方式, dfs(pos,last,cnt) 分别是位置, 上一次选的元素, 上一个元素已经选了多少个, 然而这样是会超内存的, 后来知道改成递推的方式是可以用滚动数组的, 又学到了新姿势.

#include<bits/stdc++.h>
    
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    using namespace std;
    
    typedef long long ll;
    typedef pair<int,int> pii;
    
    inline int in()
    {
        int res=0;char c;int f=1;
        while((c=getchar())<'0' || c>'9')if(c=='-')f=-1;
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res*f;
    }
    const int N=100010,MOD=1e9+7;
    int dp[2][2][301],a[2],b,n;
    
    void add(int &x,int y)
    {
        x += y;
        if(x >= MOD) x -= MOD;
    }
    
    int main()
    {
        n=in(),a[0]=in(),a[1]=in();
        dp[0][0][0]=1;  
        for(int i=0;i<n;i++){
            mem(dp[(i+1)&1],0);  //滚动数组要初始化
            for(int j=0;j<2;j++){
                for(int k=0;k<=a[j];k++){
                    if(k<a[j]){
                        add(dp[(i+1)&1][j][k+1],dp[i&1][j][k]);
                        add(dp[(i+1)&1][1-j][1],dp[i&1][j][k]);
                    }
                    else{
                        add(dp[(i+1)&1][1-j][1],dp[i&1][j][k]);
                    }
                }
            }
        }
        int ans=0;
        for(int j=0;j<2;j++){
            for(int k=1;k<=a[j];k++){
                add(ans,dp[n&1][j][k]);
            }
        }
        cout<<ans<<endl;
        return 0;
    }

[Link 1]: http://codeforces.com/gym/100507/attachments