Luogu P1373 小a和uim之大逃离【dp】By cellur925

题目传送门

$50pts$：容易设计出状态$f[i][j][l][r][st]$表示当前的这个人在（$i$,$j$），小a和uim魔瓶中的含量分别为$l$,$r$，当$st=0$表明现在是小a在吃，当$st=1$表明现在是uim吃（方案数）。注意赋初值为$f[i][j][mapp[i][j]][0][0]=1$。因为是从小a开始吃的。转移方程比较显然&麻烦，就写在代码里了。

但是还是有一些坑点的。比如模数是$k+1$，用刷表法（从当前状态推到之后状态）来防止出现负数。还和学长博客学到了一个神奇的方法：

void zy(int &x,int &y) 
{
    x=(x+y)%moder;    
}

#include<cstdio>
#include<algorithm>

using namespace std;
const int moder=1e9+7;

int n,m,k,ans;
int mapp[200][200],f[200][200][20][20][2];

void zy(int &x,int &y) 
{
    x=(x+y)%moder;    
}

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",&mapp[i][j]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            f[i][j][mapp[i][j]][0][0]=1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            for(int l=0;l<=k-1;l++)
                for(int r=0;r<=k-1;r++)
                {
                    zy(f[i+1][j][(l+mapp[i+1][j])%k][r][0],f[i][j][l][r][1]);
                    zy(f[i][j+1][(l+mapp[i][j+1])%k][r][0],f[i][j][l][r][1]);
                    zy(f[i+1][j][l][(r+mapp[i+1][j])%k][1],f[i][j][l][r][0]);
                    zy(f[i][j+1][l][(r+mapp[i][j+1])%k][1],f[i][j][l][r][0]);
                    if(l==r) (ans+=f[i][j][l][r][1])%=moder;
                }
    printf("%d",ans);
    return 0;
}

$100pts$：上面那个算法的复杂度是$O(n*m*k*k)$，复杂度显然会爆炸。考虑对dp进行优化，有优化状态和优化转移两种方法。状态貌似不能再优化了。

学长：那么这题的转移方程没有最值，没有单调性，那么我们只能优化状态。

考虑设计这样一个状态：$f[i][j][od][st]$表示当前的这个人在（$i$,$j$），小a和uim的魔瓶内含量差为$od$的方案数。与之前有相似的转移方程及初值。这样我们的复杂度就是$O(n*m*k)$，可以过。

#include<cstdio>
#include<algorithm>

using namespace std;
const int moder=1e9+7;

int n,m,k,ans;
int mapp[900][900],f[850][850][20][2];

void zy(int &x,int &y) 
{
    x=(x+y)%moder;    
}

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",&mapp[i][j]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            f[i][j][mapp[i][j]][0]=1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            for(int od=0;od<=k-1;od++)
            {
                zy(f[i+1][j][(od+mapp[i+1][j]+k)%k][0],f[i][j][od][1]);
                zy(f[i][j+1][(od+mapp[i][j+1]+k)%k][0],f[i][j][od][1]);
                zy(f[i+1][j][(od-mapp[i+1][j]+k)%k][1],f[i][j][od][0]);
                zy(f[i][j+1][(od-mapp[i][j+1]+k)%k][1],f[i][j][od][0]);
                if(od==0) (ans+=f[i][j][od][1])%=moder;
            }
    printf("%d",ans);
    return 0;
}