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

2017-08-13 19:22:31


路径行走dp+背包

审题

两个人绑在一起走,但是每次吸收的人交换,可以向右向下走,求二者魔瓶内体积相等的方案数目。

注意开始和结束都在矩阵内。

思路分析

不知道大家有没有写过一道叫做多米诺骨牌的题目。Luogu P1282

那个题目里面明显地说明了"让差最小",于是我们把差加入状态;在这个题目里面,体积相等可以转化为差为0。

因为吸取魔液实际上是建立了不同液体量,也就是不同体积之间的联系,所以同样可以用背包的方法:定义状态$f(i,j,p,q)$为处在坐标$(i,j)$,二者体积的差值(模k+1意义下)为p,q=0表示这个格子由小a吸收,反之表示由uim吸收。统计向右和向下走的方案总数目即可。

状态转移方程:

代码:注意常数,多维数组每一位都尽量不要是2的n次方,否则会不断cache miss降低效率;MOD运算很慢,减少进行的次数

#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;
}