[洛谷P1373]小a和uim之大逃离
/ / 阅读耗时 15 分钟难度：提高+/省选-
题目背景
小a和uim来到雨林中探险。突然一阵北风吹来，一片乌云从北部天边急涌过来，还伴着一道道闪电，一阵阵雷声。刹那间，狂风大作，乌云布满了天空，紧接着豆大的雨点从天空中打落下来，只见前方出现了一个披头散发，青面獠牙的怪物，低沉着声音说：“呵呵，既然你们来到这，只能活下来一个！”。小a和他的小伙伴都惊呆了！
题目描述
瞬间，地面上出现了一个n*m的巨幅矩阵，矩阵的每个格子上有一坨0~k不等量的魔液。怪物各给了小a和uim一个魔瓶，说道，你们可以从矩阵的任一个格子开始，每次向右或向下走一步，从任一个格子结束。开始时小a用魔瓶吸收地面上的魔液，下一步由uim吸收，如此交替下去，并且要求最后一步必须由uim吸收。魔瓶只有k的容量，也就是说，如果装了k+1那么魔瓶会被清空成零，如果装了k+2就只剩下1，依次类推。怪物还说道，最后谁的魔瓶装的魔液多，谁就能活下来。小a和uim感情深厚，情同手足，怎能忍心让小伙伴离自己而去呢？沉默片刻，小a灵机一动，如果他俩的魔瓶中魔液一样多，不就都能活下来了吗？小a和他的小伙伴都笑呆了！
现在他想知道他们都能活下来有多少种方法。
输入输出格式
输入格式:
第一行，三个空格隔开的整数n，m，k
接下来n行，m列，表示矩阵每一个的魔液量。同一行的数字用空格隔开。
输出格式:
一个整数，表示方法数。由于可能很大，输出对1 000 000 007取余后的结果。
输入输出格式
Sample input
2 2 3
1 1
1 1
Sample output
4
说明
[样例解释]
四种方案是:
(1，1)->(1，2)，(1，1)->(2，1)，(1，2)->(2，2)，(2，1)->(2，2)。
[数据范围]
对于20%的数据，n，m≤10，k≤2
对于50%的数据，n，m≤100，k≤5
对于100%的数据，n，m≤800，1≤k≤15
题解
考察动态规划。本题对时间空间复杂度都有考验。
规定f(a，b，x，y，t)表示在坐标(x，y)，两人魔液值为a，b(已吸收(x，y)处的)，在t状态(0表示小a吸收，1表示uim吸收)的方案数，则有递推关系:
同时有:
∂(a，b)在a=b时为1，否则为0。
答案即为$\sum f(value(x，y)，0，x，y，0)$，1≤x≤n且1≤y≤m。
这是一个5维的递推式，需要用一个5维数组储存数据，极易MLE。注意到递推式只与两个相邻行有关，可以考虑压缩数组(这个思想已经用过很多次了)。但是不能直接将其压缩至4维，这是因为其余维度的数据很难保证不被异常覆盖。这时采用滚动数组的方法，这是压缩数组维数不可行时的另一种解决方案。
滚动数组很容易理解。将控制行的一维压缩至2个元素，分别储存待计算的一行和提供递推数据的一行(即相邻的两行)。两行交替进行递推，便可递推出所有的数值。
下面给出原版代码和滚动数组优化的代码，请读者观察其区别。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
using namespace std;
int dp[16][16][805][805][2] = {0};
int op[805][805];
int n, m, k;
int main() {
cin >> n >> m >> k;
k++;//k自加,后边不用再+1
for (int i = 1; i ≤ n; i++) {
for (int j = 1; j ≤ m; j++)cin >> op[i][j];
}
for (int i = 0; i < k; i++)dp[i][i][n][m][1] = 1;//递推奠基
for (int i = n; i ≥ 1; i--) {
for (int j = m; j ≥ 1; j--) {
if (i == n && j == m)continue;
for (int a = 0; a < k; a++) {
for (int b = 0; b < k; b++) {
dp[a][b][i][j][0] = dp[a][S1(b + op[i + 1][j])][i + 1][j][1] + dp[a][S1(b + op[i][j + 1])][i][j + 1][1];
dp[a][b][i][j][1] = dp[S1(a + op[i + 1][j])][b][i + 1][j][0] + dp[S1(a + op[i][j + 1])][b][i][j + 1][0];
if (a == b)dp[a][b][i][j][1]++;
dp[a][b][i][j][0] = S2(dp[a][b][i][j][0]);
dp[a][b][i][j][1] = S2(dp[a][b][i][j][1]);
}
}
}
}
int ans = 0;
for (int i = 1; i ≤ n; i++) {
for (int j = 1; j ≤ m; j++)ans += dp[op[i][j]][0][i][j][0], ans = S2(ans);//求和
}
cout << ans;
return 0;
}
滚动数组优化版本(65分)(外加读入优化)1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
int dp[16][16][2][805][2] = {0};//第三维压至2个元素
short int op[805][805];
int n, m, k;
inline int ID(int x) {
if (x == 1)return 0;
return 1;
}
short int read() {
char e = getchar();
while (e < '0' || e > '9')e = getchar();
short int sum = 0;
while (e ≥ '0' && e ≤ '9') {
sum = sum * 10 + e - '0';
e = getchar();
}
return sum;
}
int main() {
n = read(), m = read(), k = read();
k++;
for (int i = 1; i ≤ n; i++) {
for (int j = 1; j ≤ m; j++)op[i][j] = read();
}
for (int i = 0; i < k; i++)dp[i][i][0][m][1] = 1;
bool key = true;
int ans = 0;
for (int i = n; i ≥ 1; i--) {
key = !key;//控制交替
for (int j = m; j ≥ 1; j--) {
if (i == n && j == m)continue;
for (int a = 0; a < k; a++) {
for (int b = 0; b < k; b++) {
dp[a][b][key][j][0] = dp[a][S1(b + op[i + 1][j])][!key][j][1] + dp[a][S1(b + op[i][j + 1])][key][j + 1][1];
dp[a][b][key][j][1] = dp[S1(a + op[i + 1][j])][b][!key][j][0] + dp[S1(a + op[i][j + 1])][b][key][j + 1][0];
if (a == b)dp[a][b][key][j][1]++;
if (dp[a][b][key][j][0] ≥ MOD) dp[a][b][key][j][0] -= MOD;
if (dp[a][b][key][j][1] ≥ MOD)dp[a][b][key][j][1] -= MOD;
}
}
ans += dp[op[i][j]][0][key][j][0];//答案必须即时更新,因为数组经压缩,数据得不到保存
if (ans ≥ MOD)ans -= MOD;
}
}
printf("%d", ans);
return 0;
}
但这样并不是最优解，这里需要注意到两人的魔液值其实没有实质意义，它们的差才是最重要的。
定义f(h，x，y，t)表示两人魔液值差为h(若为负则转化为k最小剩余系中与h对1+k同余的数)，其余意义不变。差值为h表示小a要么比uim多h，要么比他少1+k-h，当其中任一人的值确定时，另一人的值通过h必然唯一确定。由此可知，这样定义的差值是合理的。
容易知h=(V(0)-V(1))%(1+k)，V(0)，V(1)分别为小a，uim的魔液值。
当小a吸收p个单位的魔液时:
当uim吸收p个单位的魔液时:
实际计算中，由于计算机计算余数并不一定得到正数，故后一个式子要写成:
可知无论两人实际的魔液值为多少，只要确定了差值，经过一定的吸收变化，其差值总是唯一确定的。所以可以将前两维压缩至1维，仅表示差值的大小。0即表示两人魔液值相同。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
int dp[16][2][805][2] = {0};
short int op[805][805];
int n, m, k;
inline short int read() {
char e = getchar();
while (e < '0' || e > '9')e = getchar();
short int sum = 0;
while (e ≥ '0' && e ≤ '9') {
sum = sum * 10 + e - '0';
e = getchar();
}
return sum;
}
int main() {
n = read(), m = read(), k = read();
k++;
for (int i = 1; i ≤ n; i++) {
for (int j = 1; j ≤ m; j++)op[i][j] = read();
}
dp[0][0][m][1] = 1;
bool key = true;
int ans = 0;
for (int i = n; i ≥ 1; i--) {
key = !key;
for (int j = m; j ≥ 1; j--) {
if (i == n && j == m)continue;
for (int b = 0; b < k; b++) {
dp[b][key][j][0] = dp[S1(b - op[i + 1][j] + k)][!key][j][1] + dp[S1(b - op[i][j + 1] + k)][key][j + 1][1];
dp[b][key][j][1] = dp[S1(b + op[i + 1][j])][!key][j][0] + dp[S1(b + op[i][j + 1])][key][j + 1][0];
if (b == 0)dp[0][key][j][1]++;
if (dp[b][key][j][0] ≥ MOD) dp[b][key][j][0] -= MOD;
if (dp[b][key][j][1] ≥ MOD)dp[b][key][j][1] -= MOD;
}
ans += dp[op[i][j]][key][j][0];
if (ans ≥ MOD)ans -= MOD;
}
}
printf("%d", ans);
return 0;
}