洛谷 1373 dp 小a和uim之大逃离 良心题解

时间:2022-06-12 08:28:22

# 洛谷 1373 dp
这题还不算太难,,当初看的时候不是很理解题意,以为他们会选择两条不同的路径,导致整体思路混乱


传送门


其实理解题意和思路之后还是敲了不短的时间,一部分身体原因再加上中午休息不太好,整个人思路较乱,靠本能打了一遍代码毫无头绪。恢复了一下状态重新开打,才算是A掉

题解

设dp[i][j][l][p]为当前走到第(i, j)位,当前(a - b) % k 为l,本次是第p个人取得药,p = 0为a,p = 1 为b,

此时的方案数

则 dp[i][j][l][1] += dp[i-1][j][((l + a[i][j]) % k + k) % k][0] + dp[i][j-1][((l + a[i][j]) % k + k) % k][0]

dp[i][j][l][0] += dp[i-1][j][((l - a[i][j]) % k + k) % k][1] + dp[i][j-1][((l - a[i][j]) % k + k) % k][1]

举个栗子:

假设本次在(3, 2),该1(uim)走,则该状态的上一个状态应为 当前在(3,1),该0(小a)走,当时的差为l + a[i][j] 另一个状态同理。

解释一下差加减的原理:

我们的dp方程的第三维定义的是a(小a) - b(uim)的差,那么按照上面的栗子来看,本步由uim来走,那么它们状态的差应减少,减少值为a[i][j],所以上一状态为l + a[i][j],

扯一点关于初始化的东西

由于题目中规定可以从每个点开始,同时必须小a先吸收,所以

对于读入的每一个a[i][j],设dp[i][j][a[i][j] % k][0] = 1

其余点均为0

关于k

实在有些不理解出题人的脑洞,,(lzn别打我= =),,只有k的容量,到了k+1就会清零,,,默默地k++吧

关于复杂度

记录两个人的当前值肯定会T,使用long long会M,据说常数太大会卡两个,暂时没发现

关于差值问题:

有人说差值可正可负,我当时也考虑了一段时间,后来发现在%k意义下对答案没有任何影响,即 k = 3时,(k + 1等于4时)a比b少2和a比b多2其实是等效的,即a拿2个后两人均相同

代码如下:

#include <cstdio>
#include <cstring>
#include <algorithm> const int maxn = 800 + 1;
const int mod = 1000000007;
int dp[maxn][maxn][16][2];
int a[maxn][maxn];
int n, m, k; 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", &a[i][j]);
dp[i][j][(a[i][j]) % k][0] = 1;
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
for (int l = 0; l < k; l++) {
dp[i][j][l][1] = (dp[i][j][l][1] + dp[i-1][j][((l + a[i][j]) % k + k) % k][0] + dp[i][j-1][((l + a[i][j]) % k + k) % k][0]) % mod;
dp[i][j][l][0] = (dp[i][j][l][0] + dp[i-1][j][((l - a[i][j]) % k + k) % k][1] + dp[i][j-1][((l - a[i][j]) % k + k) % k][1]) % mod;
}
}
}
long long ans = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
ans = (ans + dp[i][j][0][1]) % mod;
}
printf("%lld", ans); return 0;
}