【算法】DP

【题解】f[i][j][0]表示在i,j位置往下走的球数，f[i][j][1]表示在i,j位置往右走的球数，经过i,j的球若为-1则(num+1)/2往下，其余往右。+1类似。

转移见代码。

#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;int read(){    char c;int s=0,t=1;    while(!isdigit(c=getchar()))if(c=='-')t=-1;    do{s=s*10+c-'0';}while(isdigit(c=getchar()));    return s*t;}const int maxn=1010;int a[maxn][maxn],n,m;long long f[maxn][maxn][2],k;int main(){    scanf("%d%d%lld",&m,&n,&k);    f[0][1][0]=k;    for(int i=1;i<=n;i++)    for(int j=1;j<=m;j++)    a[i][j]=read();    for(int i=1;i<=n;i++)    for(int j=1;j<=m;j++)    {        long long num=f[i-1][j][0]+f[i][j-1][1];        if(a[i][j]==-1)f[i][j][0]=(num+1)/2,f[i][j][1]=num-(num+1)/2;        if(a[i][j]==1)f[i][j][1]=(num+1)/2,f[i][j][0]=num-(num+1)/2;        if(a[i][j]==0)f[i][j][0]=f[i-1][j][0],f[i][j][1]=f[i][j-1][1];    }    printf("%lld",f[n][m][0]);    return 0;}