钻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;