思路:dp.
dp[i][j][s]
如果s为1,表示第i层长度为j且至少包含一段>=d的距离的路径数
如果s为0,表示第i层长度为j且不包含一段>=d的距离的路径数
状态转移看代码
代码:
#include<bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define mem(a,b) memset(a,b,sizeof(a)) const int MOD=1e9+7; const int N=105; ll dp[N][N][2]; int main(){ ios::sync_with_stdio(false); cin.tie(0); int n,k,d; cin>>n>>k>>d; for(int i=1;i<=k;i++)if(i>=d)dp[1][i][1]=1;else dp[1][i][0]=1; for(int i=2;i<=n;i++){ for(int j=1;j<=n;j++){ for(int ii=1;ii<=min(j,k);ii++){ if(ii>=d)dp[i][j][1]=(dp[i][j][1]+dp[i-1][j-ii][1]+dp[i-1][j-ii][0])%MOD; else dp[i][j][0]=(dp[i][j][0]+dp[i-1][j-ii][0])%MOD,dp[i][j][1]=(dp[i][j][1]+dp[i-1][j-ii][1])%MOD; } //cout<<dp[i][j][1]<<' '; } //cout<<endl; } ll ans=0; for(int i=1;i<=n;i++)ans=(ans+dp[i][n][1])%MOD; cout<<ans<<endl; return 0; }