点击打开链接
题意:n个点1~n,初始在a点,禁止到b点,操作:每次可以从x到y点,当且仅当x!=y并且|x-y|<|x-b|.
问k次操作后能得到多少个不同的序列? n,k<=5000 设dp[j][i] 从i开始,操作j次能得到的方法数 mx=|i-b|-1,当mx>=1时:dp[j][i]+= dp[j-1][i-mx~i+mx]用前缀和优化到O(N^2)即可
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=5e3+20; const ll mod=1e9+7; int n,a,b,k; ll dp[N][N],pre[N]; int main() { while(cin>>n>>a>>b>>k) { memset(pre,0,sizeof(pre)); memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++) dp[0][i]=1,pre[i]=pre[i-1]+dp[0][i]; dp[1][b]=0; for(int j=1;j<=k;j++) { for(int i=1;i<=n;i++) { int mx=abs(i-b)-1; if(mx==0||i==b) dp[j][i]=0; else { int l=max(1,i-mx); int r=min(n,i+mx); dp[j][i]=(pre[r]-pre[l-1]+mod)%mod; dp[j][i]=(dp[j][i]-dp[j-1][i]+mod)%mod; } } pre[0]=0; for(int i=1;i<=n;i++) pre[i]=(pre[i-1]+dp[j][i])%mod; } cout<<dp[k][a]<<endl; } return 0; }