P1373 小a和uim之大逃离四维dp，维护差值

绝地灬酷狼 2023-06-04 08:00 3阅读 0赞

[**题目链接**][Link 1]

**对于这道题，dp是显然的，不过状态设计就比较奇葩，dp\[i\]\[j\]\[h\]\[which\]表示在第i行，第j列，差值为h，0表示小a，1表示uim。哪一个人which取到了宝物，不用去记录他们两个人的值，维护差值转移即可。如果超过k+1的话，就直接膜就可以了。**

**初始状态：dp\[i\]\[j\]\[a\[i\]\[j\]\]\[0\]=1。（因为是小a先取）枚举i，j，h转移，h的差值不超过k**

**转移方程：**

**dp\[i\]\[j\]\[h\]\[0\]+=dp\[i-1\]\[j\]\[h-a\[i\]\[j\]\]\[1\]%mod;小a的转移从uim来，取了a\[i\]\[j\]差值就从h增大了，从上方左边转移而来  
dp\[i\]\[j\]\[h\]\[0\]+=dp\[i\]\[j-1\]\[h-a\[i\]\[j\]\]\[1\]%mod;  
dp\[i\]\[j\]\[h\]\[1\]+=dp\[i-1\]\[j\]\[h+a\[i\]\[j\]\]\[0\]%mod;uim同理，只不过他取了过后差值减小，转移同理  
dp\[i\]\[j\]\[h\]\[1\]+=dp\[i\]\[j-1\]\[h+a\[i\]\[j\]\]\[0\]%mod;**

**最后累加dp\[i\]\[j\]\[0\]\[1\]的答案即可，因为最后他俩的数量一样，差值为0，最后是uim取。**

**代码：**

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    using namespace std;
    const int N=950;
    const int mod=1000000007;
    int ditu[N][N];
    int dp[N][N][18][2];
    long long ans;
    int 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",&ditu[i][j]);
                dp[i][j][ditu[i][j]][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][0]+=dp[i-1][j][(h-ditu[i][j]+k)%k][1]%mod;
                    dp[i][j][h][0]+=dp[i][j-1][(h-ditu[i][j]+k)%k][1]%mod;
                    dp[i][j][h][1]+=dp[i-1][j][(h+ditu[i][j]+k)%k][0]%mod;
                    dp[i][j][h][1]+=dp[i][j-1][(h+ditu[i][j]+k)%k][0]%mod;
                }
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                ans=(ans+dp[i][j][0][1])%mod;
            }
        }
        printf("%lld\n",ans);
        return 0;
    }

转载于:https://www.cnblogs.com/LJB666/p/11366869.html

[Link 1]: https://www.luogu.org/problem/P1373
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/9bab86dd880f4013a7da71dd55921e6b.png