牛客巅峰赛s2第六场c

钻b，铜c dp https://www.bilibili.com/video/BV1sZ4y1g74R?p=3

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef vector<int> vii;
typedef vector<ll> vll;
typedef pair<int,int> PII;
#define so sizeof
#define pb push_back
#define fi first
#define se second
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
void readvii(vii &a){
    char c;int num=0;
    while(getchar()!='[') ;
    while(c=getchar()){
        if(c==']'){
            a.pb(num); break;
        }else if(isdigit(c)){
            num=num*10+(c-'0');
        }else{
            a.pb(num); num=0;
        }
    }
}

const db esp=1e-5;
const int N=1e3+10,M=1e2+10,Max=1e5+5,inf=0x3f3f3f3f,mod=1000000007;
const ll INF=0x3f3f3f3f3f3f3f3f;

ll dp[N][N][2];
class Solution {
public:
    /**
     *
     * @param n int整型 乐谱总音符数
     * @param m int整型 重音符数
     * @param k int整型 重音符之间至少的间隔
     * @return long长整型
     */
    long long solve_bangbang(int n, int m, int k) {
        // write code here
        dp[0][0][0]=1;
        for(int i=1;i<=n;i++){
            dp[i][0][0]=1;
            for(int j=1;j<=m;j++){
                if(j==1) dp[i][1][1]+=dp[i-1][0][0], dp[i][1][1]%=mod;
                else if(i-k-1>=0) dp[i][j][1]=dp[i-k-1][j-1][1]+dp[i-k-1][j-1][0]; dp[i][j][1]%=mod;
                dp[i][j][0]+=dp[i-1][j][1]+dp[i-1][j][0]; dp[i][j][0]%=mod;
            }
        }
        return (dp[n][m][0]+dp[n][m][1])%mod;
    }

}T;