Sum of Paths CodeForces - 1467D
Tagscombinatorics dp math *2200

題意：

定義一條好的路徑，當且僅當從任意點出發之后恰好經過了 k 次移動，定義這條路徑的權值為經過點權值的總和(可重)，進行 q 次修改，每次將ak 改為 x ,詢問此時所有‘好’路徑的權值總和.
例如樣例：

5 1 5 3 5 1 4 2 1 9 2 4 3 6 4 6 5 2

將第一位換成9就成了9 5 1 4 2 ，對應的答案就是62

題解：

dp動態規劃
根據題目，我們要計算每個格子的貢獻，設dp[i][j]表示走了j步當前在i點的路徑總數
i點可能是從i-1來的也可能是i+1來的
狀態轉移：
dp[i][k] = dp[i-1][k-1] + dp[i+1][k-1]
dp[i][k]也可以理解成在i點還需要走k步才能到達任意點的路徑總數（相當于反著想）
那么怎么考慮每個點的貢獻？
如果當前點i走了m步，方案數是dp[i][m],因為一共走k步，所以還有k-m步要走，方案數是dp[i][m-k]，該點貢獻就是∑_m=0^m=kdp[i][m] * dp[i][m-k]
對于每次修改，修改第i點的值，先減去原本第i點的貢獻，再加新的貢獻

代碼：

#include<bits/stdc++.h> typedef long long ll; using namespace std; inline int read(){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);return s*w; } const int maxn=5e3+9; const int mod=1e9+7; ll a[maxn],c[maxn]; ll dp[maxn][maxn]; int main() {int n,k,p;cin>>n>>k>>p;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++)dp[i][0]=1;for(int i=1;i<=k;i++)//步數 {for(int j=1;j<=n;j++)//當前格子 {dp[j][i]=(dp[j-1][i-1]+dp[j+1][i-1])%mod;}}ll sum=0;for(int i=1;i<=n;i++)//當前格子 {for(int j=0;j<=k;j++){c[i]=(c[i]+(dp[i][j]*dp[i][k-j])%mod)%mod;}}for(int i=1;i<=n;i++)sum=(sum+(a[i]*c[i])%mod)%mod;for(int i=1;i<=p;i++){ll pos,x;cin>>pos>>x;sum=((sum-(a[pos]*c[pos])%mod)%mod+mod)%mod;a[pos]=x;sum=(sum+(a[pos]*c[pos])%mod)%mod;printf("%lld\n",sum);}return 0; } /* Input 5 1 5 3 5 1 4 2 1 9 2 4 3 6 4 6 5 2 Output 62 58 78 86 86 */

總結

以上是生活随笔為你收集整理的Sum of Paths CodeForces - 1467D的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。