CF695 D. Sum of Paths（DP）

CF695 D. Sum of Paths（DP）

传送门

题意：给一个长度为n的区域，你可以任选起点走k步，每步可以向左或向右。同时每个点都有权值，走到点上即可加权值，问所有走的方案的权值之和，再有q次询问每次会更改一点权值，再求和。

题解：可恶的带修询问卡掉了我的记忆化搜索，不然就是个水题。有带修的话，就只能先计算出每个点经过的次数，再O（1）更新答案。

考虑dp，设dp[i] [j]，表示第j步踩在i点上的方案数，易得dp[i] [j]=dp[i] [j-1]+dp[i] [j]，主要问题是第j步踩在i点时，之后还有延续，有分枝，简单求和是一个肯定错误的答案，想了很久，一直不知道怎么处理，看完题解我只能说真的太巧了，自己也太蠢了，想不到。dp[i] [j]表示的j步后到i点，那么同时也可以视为起点为i，走j步可以走的方案数，那么dp[i] [j]的延续数不就是dp[i] [k-j]吗？解决这个问题，此问题就迎刃而解了。

#include<iostream>
using namespace std;
#define ll long long
const ll mod=1e9+7;
ll n,k,q;
ll a[20007],dp[5007][5007],cnt[5007];
void init(){
	for(int i=1;i<=n;i++){
		dp[i][0]=1;
	}
	for(int j=1;j<=k;j++){
		for(int i=1;i<=n;i++){
			if(i==1){
				dp[i][j]=dp[i+1][j-1];
			}
			else if(i==n){
				dp[i][j]=dp[i-1][j-1];
			}
			else{
				dp[i][j]=(dp[i-1][j-1]+dp[i+1][j-1])%mod;
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=0;j<=k;j++){
			cnt[i]=(cnt[i]+dp[i][j]*dp[i][k-j]%mod)%mod;
		}
	}
}
int main(){
	scanf("%lld%lld%lld",&n,&k,&q);
	init();
	ll sum=0;
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		sum=(sum+cnt[i]*a[i]%mod)%mod;
	}
	ll p,x;
	while(q--){
		scanf("%lld%lld",&p,&x);
		sum=(sum-a[p]*cnt[p]%mod+mod)%mod;
		a[p]=x;
		sum=(sum+a[p]*cnt[p]%mod)%mod;
		printf("%lld
",sum);
	}
}