CF 479E Riding in a Lift 前綴和 DP

CF 479E Riding in a Lift 前綴和 DP

輸入 n a b k 有n層樓 起點在a層 b層是不能到達的 假設當前在x層 每一次可以到達y層 滿足 |x-y| < |x-b| 求進行k次的不同方案數

dp[i][j]為第i次到達j層的方案數 dp[i][j] = sum(dp[i-1][k]) 其中|k-j| < |k-b|

滿足條件的k是連續的一段 用前綴和優化

#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int maxn = 5010;
const int mod = 1000000007;
LL dp[maxn][maxn];
int main()
{
	int n, a, b, m;
	while(scanf("%d %d %d %d", &n, &a, &b, &m) != EOF)
	{
		memset(dp, 0, sizeof(dp));
		for(int i = a; i <= n; i++)
			dp[0][i] = 1;
		for(int i = 1; i <= m; i++)
		{
			for(int j = 1; j <= n; j++)
			{
				if(j == b)
				{
					dp[i][j] += dp[i][j-1];
					continue;
				}
				if(j < b)
				{
					int d = b-j;
					int x = j+(b-j-1)/2;
					dp[i][j] += dp[i-1][x]-(dp[i-1][j]-dp[i-1][j-1]);
					dp[i][j] %= mod;
				}
				else
				{
					int d = j-b;
					int x = j-(j-b-1)/2;
					dp[i][j] += dp[i-1][n]-dp[i-1][x-1]-(dp[i-1][j]-dp[i-1][j-1]);
				}
				dp[i][j] += dp[i][j-1];
				dp[i][j] %= mod;
			}	
		}
		//for(int j = 1; j <= n; j++)
		printf("%I64d\n", (dp[m][n]+mod)%mod);
	}
	return 0;
}