这是一道dp好题

咱们读读题

 

题意就是求到达某一点使得两人获取的能量一样

本蒟蒻一开始想了半天都没能把两者能量一样转换成两者差为0

若能这么转换，dp方程就能得出来了

dp[i][j][h][1]=(dp[i][j][h][1]+dp[i-1][j][(h+d[i][j])%k][0])%mod;

dp[i][j][h][1]=(dp[i][j][h][1]+dp[i][j-1][(h+d[i][j])%k][0])%mod;

dp[i][j][h][0]=(dp[i][j][h][0]+dp[i-1][j][(h-d[i][j]+k)%k][1])%mod;

dp[i][j][h][0]=(dp[i][j][h][0]+dp[i][j-1][(h-d[i][j]+k)%k][1])%mod;

i，j表示到达的位置坐标为 i，j

h表示两者获得的能量之差（小a-uim）

0表示当前走的人是小a，1表示当前走的人是uim

状态转移就如上

当前是1时，就是由上一个点的差值加上这个点的值

当前是0时，就是由上一个点的差值在减去这个点的值

不要忘记%k

先看看代码，后面会讲解坑点

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;typedef long long ll;const int mod=1000000007;const int N=805;int dp[N][N][20][2],d[N][N],n,m,k;int main(){    scanf("%d %d %d",&n,&m,&k);    k++;    for(int i=1;i<=n;i++)        for(int j=1;j<=m;j++)        {            scanf("%d",&d[i][j]);            dp[i][j][d[i][j]%k][0]=1;        }    for(int i=1;i<=n;i++)        for(int j=1;j<=m;j++)        {            for(int h=0;h<=k;h++)            {                dp[i][j][h][1]=(dp[i][j][h][1]+dp[i-1][j][(h+d[i][j])%k][0])%mod;                dp[i][j][h][1]=(dp[i][j][h][1]+dp[i][j-1][(h+d[i][j])%k][0])%mod;                dp[i][j][h][0]=(dp[i][j][h][0]+dp[i-1][j][(h-d[i][j]+k)%k][1])%mod;                dp[i][j][h][0]=(dp[i][j][h][0]+dp[i][j-1][(h-d[i][j]+k)%k][1])%mod;            }        }    int ans=0;    for(int i=1;i<=n;i++)        for(int j=1;j<=m;j++)        {            ans=(ans+dp[i][j][0][1])%mod;        }    printf("%d\n",ans);}
         
        
       
      
     

注意：

1.一开始的初始化，应该把小a放在每个点所获得的能量值都求出来

2.%运算是有优先级的

　　上述式子就不能写成dp[i][j][h][1]+=dp[i-1][j][(h+d[i][j])%k][0]%mod，因为这是先给后面取模，在进行加法运算，

　　这里坑了我很久

3.因为减法会产生负数，所以要加上k在取模

4.这题还卡空间，如果定成long long 就会爆掉

5.别忘记k++，看清楚题

差不多都讲完了，希望对你们有帮助