题解 P1373 【小a和uim之大逃离】

路径行走dp+背包 ### 审题 两个人绑在一起走，但是每次吸收的人交换，可以向右向下走，求二者魔瓶内体积相等的方案数目。 注意开始和结束都在矩阵内。 ### 思路分析 不知道大家有没有写过一道叫做多米诺骨牌的题目。[Luogu P1282](https://www.luogu.org/problem/show?pid=1282) 那个题目里面明显地说明了"让差最小"，于是我们把差加入状态；在这个题目里面，体积相等可以转化为差为0。 因为吸取魔液实际上是建立了不同液体量，也就是不同体积之间的联系，所以同样可以用背包的方法：定义状态$f(i,j,p,q)$为处在坐标$(i,j)$，二者体积的差值（模k+1意义下）为p，q=0表示这个格子由小a吸收，反之表示由uim吸收。统计向右和向下走的方案总数目即可。 状态转移方程：  代码：注意常数，多维数组每一位都尽量不要是2的n次方，否则会不断cache miss降低效率；MOD运算很慢，减少进行的次数 ```cpp #include <cstdio> #include <cstring> #include <cstdlib> #include <cctype> using namespace std; const int MAXN = 800, MAXM = 800, MAXK = 15, MOD=1e9+7; int N,M,K,n1,n2,Ans,W[MAXN+2][MAXM+2],opt[MAXN+2][MAXM+2][MAXK+2][2];//85MB inline int readint() { int f=1,r=0;char c=getchar(); while(!isdigit(c)){if(c=='-')f=-1;c=getchar();} while(isdigit(c)){r=r*10+c-'0';c=getchar();} return f*r; } int main(){ N=readint();M=readint();K=readint(); for(int i=1;i<=N;i++) for(int j=1;j<=M;j++) W[i][j]=readint(); for(int i=N;i>=1;i--) for(int j=M;j>=1;j--) for(int p=0;p<=K;p++) { n1=(p+W[i][j])%(K+1);n2=(p-W[i][j]%(K+1)+((K+1)<<1))%(K+1); //q=0 opt[i][j][p][0] = (opt[i][j][p][0]%MOD + opt[i+1][j][n1][1]%MOD) %MOD; opt[i][j][p][0] = (opt[i][j][p][0]%MOD + opt[i][j+1][n1][1]%MOD) %MOD; //q=1 opt[i][j][p][1]= (opt[i][j][p][1]%MOD + opt[i+1][j][n2][0]%MOD) %MOD; opt[i][j][p][1] = (opt[i][j][p][1]%MOD + opt[i][j+1][n2][0]%MOD) %MOD; //Stop here if(n2==0) opt[i][j][p][1]++; } for(int i=1;i<=N;i++) for(int j=1;j<=M;j++) Ans=(Ans%MOD+opt[i][j][0][0]%MOD)%MOD; printf("%d",Ans); return 0; } ```