题意：给出一个n*m的矩阵，每个格子有一定的能量（小于k）
有一人有两个瓶子，瓶子可以吸收能量，得出的结果mod(k+1)
可以从任意位置开始，但只能向下或者向右走，走偶数步数即可结束
求两个瓶子能量相等的方案数
思路：四维DP【i】【j】【h】【0/1】 表示在（i，j）这个位置时存储了h能量（两个瓶子能量差值)，为奇数步或偶数步的方案数
然后枚举即可，枚举起来跟二维没差别；
最后再把答案得出
遇到的问题：一开始我开成了五维，就是把h这一维分了出来，分了第一个瓶子和第二个瓶子分别存储了多少能量
然后我就开始递推，可是就是得不出来，然后换了四维才过。
不过我还是觉得五维可以过，只是mle hhhhh 因为四维稍微开大一点也mle了 hhh
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int mod=1e9+7; 4 const int maxn=8e2+10; 5 int dp[maxn][maxn][20][2]; 6 int a[maxn][maxn]; 7 int main() 8 { 9 int n,m,k; 10 scanf("%d%d%d",&n,&m,&k); 11 k++; 12 for(int i=1;i<=n;i++) 13 for(int j=1;j<=m;j++){ 14 scanf("%d",&a[i][j]); 15 dp[i][j][a[i][j]][1]=1; 16 } 17 int ans=0; 18 for(int i=1;i<=n;i++) 19 for(int j=1;j<=m;j++){ 20 for(int h=0;h<k;h++){ 21 int tmp=a[i][j]; 22 dp[i][j][h][0]=(dp[i][j][h][0]+dp[i-1][j][((h+tmp)%k+k)%k][1])%mod; 23 dp[i][j][h][0]=(dp[i][j][h][0]+dp[i][j-1][((h+tmp)%k+k)%k][1])%mod; 24 dp[i][j][h][1]=(dp[i][j][h][1]+dp[i-1][j][((h-tmp)%k+k)%k][0])%mod; 25 dp[i][j][h][1]=(dp[i][j][h][1]+dp[i][j-1][((h-tmp)%k+k)%k][0])%mod; 26 } 27 } 28 for(int i=1;i<=n;i++) 29 for(int j=1;j<=m;j++){ 30 ans=(ans+dp[i][j][0][0])%mod; 31 } 32 printf("%d\n",ans); 33 return 0; 34 }
原文：https://www.cnblogs.com/pangbi/p/12606588.html
