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

以后再开三维以上的数组一定算内存= = 原题： 瞬间，地面上出现了一个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坠吼 代码： ```cpp #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; } ```