洛谷 P1373 小a和uim之大逃离 题解

每日一题 day30 打卡

Analysis

f[i][j][p][q]表示他们走到(i,j)，且两人魔瓶内魔液量的差为p时的方法数。q=0表示最后一步是小a走的，q=1表示最后一步是uim走的。题目中说魔瓶的容量为k，实际上就是动归时p需要对k+1取余数，即p只有0~k，k+1种可能。答案为所有f[i][j][0][1]的和。

动归方程如下：（为了方便已经令k=k+1）

f[i][j][p][0]+=f[i-1][j][(p-mapp[i][j]+k)%k][1] (i-1>=1)

f[i][j][p][0]+=f[i][j-1][(p-mapp[i][j]+k)%k][1] (j-1>=1)

f[i][j][p][1]+=f[i-1][j][(p+mapp[i][j])%k][0] (i-1>=1)

f[i][j][p][1]+=f[i][j-1][(p+mapp[i][j])%k][0] (j-1>=1)

还有每个格子都有可能作为小a的起始格子，所以初始时对于所有i、j，f[i][j][mapp[i][j]][0]=1。

算法复杂度o(n*m*k)

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define maxn 800+10

 #define mod 1000000007

 using namespace std;

 inline int read()

 {

     int x=;

     bool f=;

     char c=getchar();

     for(; !isdigit(c); c=getchar()) if(c=='-') f=;

     for(; isdigit(c); c=getchar()) x=(x<<)+(x<<)+c-'';

     if(f) return x;

     return -x;

 }

 inline void write(long long x)

 {

     if(x<){putchar('-');x=-x;}

     if(x>)write(x/);

     putchar(x%+'');

 }

 int n,m,k;

 int map[maxn][maxn];

 int dp[maxn][maxn][][];

 int main()

 {

     n=read();m=read();k=read();

     k++;

     for(int i=;i<=n;i++)

         for(int j=;j<=m;j++)

         {

             map[i][j]=read();

             dp[i][j][map[i][j]][]=;

         }

     long long ans=;

     for(int i=;i<=n;i++)

         for(int j=;j<=m;j++)

             for(int p=;p<=k;p++)

             {

                 dp[i][j][p][]=(dp[i][j][p][]+dp[i-][j][(p-map[i][j]+k)%k][])%mod;

                 dp[i][j][p][]=(dp[i][j][p][]+dp[i][j-][(p-map[i][j]+k)%k][])%mod;

                 dp[i][j][p][]=(dp[i][j][p][]+dp[i-][j][(p+map[i][j])%k][])%mod;

                 dp[i][j][p][]=(dp[i][j][p][]+dp[i][j-][(p+map[i][j])%k][])%mod;

             }

     for(int i=;i<=n;i++)

         for(int j=;j<=m;j++)

             ans=(ans+dp[i][j][][])%mod;

     write(ans);

     return ;

 }

请各位大佬斧正