【洛谷1373】小a和uim之大逃离

2018-03-18 21:54:50


以后再开三维以上的数组一定算内存= =
原题:
瞬间,地面上出现了一个n*m的巨幅矩阵,矩阵的每个格子上有一坨0~k不等量的魔液。怪物各给了小a和uim一个魔瓶,说道,你们可以从矩阵的任一个格子开始,每次向右或向下走一步,从任一个格子结束。开始时小a用魔瓶吸收地面上的魔液,下一步由uim吸收,如此交替下去,并且要求最后一步必须由uim吸收。魔瓶只有k的容量,也就是说,如果装了k+1那么魔瓶会被清空成零,如果装了k+2就只剩下1,依次类推。怪物还说道,最后谁的魔瓶装的魔液多,谁就能活下来。小a和uim感情深厚,情同手足,怎能忍心让小伙伴离自己而去呢?沉默片刻,小a灵机一动,如果他俩的魔瓶中魔液一样多,不就都能活下来了吗?小a和他的小伙伴都笑呆了!

现在他想知道他们都能活下来有多少种方法。

n,m<=800,1<=k<=15

题很简单,就记几个注意事项
首先注意题目中没说输进来的数<=k,所以要先膜(第一次写的时候不知道怎么痿事居然以为有这个条件
首先一个显然的思路是f[i][j][p][q]记录在点(i,j)第一个人装了p第二个人装了q
然后错了,因为可以从任一点出发,所以i+j的奇偶并不能表示当前是哪个人
顺带一提,如果从(1,1)开始走,用i+j判断在网格图上对角线单向走的步数的奇偶,i+j为偶数的时候是奇数步,奇数的时候是偶数步
那可以用f[i][j][k][p][q],k为0或1表示当前是哪个人
然后:

非常神奇 后来在宋逸群的指导下发现我开的f[810][810][2][20][20]
算一下内存,差不多5个g,我校电脑内存甚至只有4G,干脆直接跑不起来

容易想到优化,用f[i][j][k][p],其中p表示两个人的差值
然后继续MLE……
算了一下,大概155M,题目要求128M……
md有毒吧
遭不住了去看题解,发现其实不用考虑两人差值为负的情况,p那一维作差的时候加上膜数再膜即可,因为瓶子会一直倒而我们只需要考虑最后差值为0的情况,所以两种写法是等效的
最后终于卡过去了
辣鸡卡空间题,512M坠吼
代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
int mo=(int)1e9+7;
int rd(){int z=0,mk=1;  char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')mk=-1;  ch=getchar();}
    while(ch>='0'&&ch<='9'){z=(z<<3)+(z<<1)+ch-'0';  ch=getchar();}
    return z*mk;
}
int n,m,o,a[810][810];
int f[810][810][2][16];
int main(){//freopen("ddd.in","r",stdin);
    cin>>n>>m>>o;
    for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)  a[i][j]=rd()%mo;
    for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)
        //f[i][j][1][o+a[i][j]]=1;
        f[i][j][1][a[i][j]]=1;
    for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)
        //for(int k=-o;k<=o;++k){
        for(int k=0;k<=o;++k){
            //f[i+1][j][0][o+(k-a[i+1][j])%(o+1)]=(f[i+1][j][0][o+(k-a[i+1][j])%(o+1)]+f[i][j][1][o+k])%mo;
            f[i+1][j][0][(k-a[i+1][j]+o+1)%(o+1)]=(f[i+1][j][0][(k-a[i+1][j]+o+1)%(o+1)]+f[i][j][1][k])%mo;
            f[i+1][j][1][(k+a[i+1][j])%(o+1)]=(f[i+1][j][1][(k+a[i+1][j])%(o+1)]+f[i][j][0][k])%mo;
            //f[i][j+1][0][o+(k-a[i][j+1])%(o+1)]=(f[i][j+1][0][o+(k-a[i][j+1])%(o+1)]+f[i][j][1][o+k])%mo;
            f[i][j+1][0][(k-a[i][j+1]+o+1)%(o+1)]=(f[i][j+1][0][(k-a[i][j+1]+o+1)%(o+1)]+f[i][j][1][k])%mo;
            f[i][j+1][1][(k+a[i][j+1])%(o+1)]=(f[i][j+1][1][(k+a[i][j+1])%(o+1)]+f[i][j][0][k])%mo;
        }
    int bwl=0;
    for(int i=1;i<=n;++i)for(int j=1;j<=m;++j){
        bwl=(bwl+f[i][j][0][0])%mo;
        //if(f[i][j][0][o])  cout<<i<<" "<<j<<endl;
    }
    cout<<bwl<<endl;
    return 0;
}