1467D.Sum of Paths(DP)

从左到右有n个单元,编号为1,2,…,n。首先,您必须在任何单元上放置一个机器人。机器人必须精确地进行k次移动。

一步移动,机器人必须向左或向右移动一个单元格,前提是它不会超出范围。换句话说,如果机器人在单元格i中,则它必须移动到单元格i-1或单元格i + 1,只要它位于1和n之间(包括端点)即可。单元按访问顺序(包括放置机器人的单元)一起构成一条良好的路径。

每个像元i都有一个与之关联的值ai。令c0,c1,...,ck为按访问顺序排列的一条路径中的单元格顺序(c0是最初放置机器人的单元格,c1是机器人第一次移动后所在的单元格,依此类推;更正式地说,ci是机器人在我移动后所处的单元)。然后,将路径的值计算为ac0 + ac1 +⋯+ ack。

您的任务是计算所有可能的良好路径上的值之和。由于此数字可能非常大,因此请以109 + 7模输出。如果起始单元格不同或存在一个整数i∈[1,k],则两个好的路径被认为是不同的,从而使i精确移动后的机器人当前单元格在这些路径中不同。

您必须将q个更新处理为a并每次打印更新后的总和。每次更新都会更改一个单元格的值。有关更多详细信息,请参见输入格式和样本输入输出。

#include<bits/stdc++.h>
using namespace std;
const int maxn=5005;
const int mod=1e9+7;
typedef long long ll;
int n,m,q;
ll a[maxn],c[maxn],f[maxn][maxn];
int main () {
    scanf("%d%d%d",&n,&m,&q);
    for (int i=1;i<=n;i++) scanf("%d",a+i);
    for (int i=1;i<=n;i++) f[i][0]=1;
    for (int k=1;k<=m;k++) for (int i=1;i<=n;i++) f[i][k]=(f[i-1][k-1]+f[i+1][k-1])%mod;
    for (int i=1;i<=n;i++) for (int k=0;k<=m;k++) c[i]=(c[i]+f[i][k]*f[i][m-k]%mod)%mod;
    ll ans=0;
    for (int i=1;i<=n;i++) ans+=a[i]*c[i]%mod,ans%=mod;
    for (int i=1;i<=q;i++) {
        int x,y;
        scanf("%d%d",&x,&y);
        ans-=a[x]*c[x]%mod;
        ans=(ans+mod)%mod;
        a[x]=y;
        ans+=a[x]*c[x]%mod;
        ans%=mod;
        printf("%lld\n",ans);
    }
} 

 

上一篇:跑yolov3模型,我遇到了No labels found. Recommend correcting image and label paths.


下一篇:Winscp 密钥登录