二维dp的回溯以及四维dp
P1005 NOIP 2007 提高组] 矩阵取数游戏 - 洛谷
这题我一开始用两次二维dp解，每次取最优路（类似贪心）。可是我不会dp回溯，于是有了以下题解：
二维dp的回溯
如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
| void back(int x, int y) {
if (x == 1 && y == 1) {
return;
}
if (x > 1 && dp[x - 1][y] + a[x][y] == dp[x][y]) {
back(x - 1, y);
}
else if (y > 1 && dp[x][y - 1] + a[x][y] == dp[x][y]) {
back(x, y - 1);
}
}
|
很好懂吧，因为每次dp取得都是到当前格的最大值，因此路径一定存在，一步步减回去就行。
完整码如下：
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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
| #include<bits/stdc++.h>
using ll = long long;
using namespace std;
const int N=1e9+5;
int dp1[11][11], dp2[11][11];
int a[11][11];
void back(int x, int y) {
if (x == 1 && y == 1) {
a[x][y] = 0;
return;
}
if (x > 1 && dp1[x - 1][y] + a[x][y] == dp1[x][y]) {
a[x][y] = 0;
back(x - 1, y);
}
else if (y > 1 && dp1[x][y - 1] + a[x][y] == dp1[x][y]) {
a[x][y] = 0;
back(x, y - 1);
}
}
void solve(){
int n; cin >> n;
while(1) {
int x, y, z;
cin >> x >> y >> z;
if (x == 0 && y == 0 && z == 0) {
break;
}
else {
a[x][y] = z;
}
}
int sum = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
dp1[i][j] = max(dp1[i - 1][j], dp1[i][j - 1]) + a[i][j];
}
}
sum += dp1[n][n];
back(n, n);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
dp2[i][j] = max(dp2[i - 1][j], dp2[i][j - 1]) + a[i][j];
}
}
sum += dp2[n][n];
cout << sum << endl;
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int _=1;
while(_--)
solve();
return 0;
}
|
注意两点：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| void back(int x, int y) {
if (x == 1 && y == 1) {
a[x][y] = 0;
return;
}
if (x > 1 && dp1[x - 1][y] + a[x][y] == dp1[x][y]) {
a[x][y] = 0;
back(x - 1, y);
}
else if (y > 1 && dp1[x][y - 1] + a[x][y] == dp1[x][y]) {
a[x][y] = 0;
back(x, y - 1);
}
}
|
果然pa了，因为当前最优不代表全局最优，贪心思路不可行，反例：
7
1 2 2
1 3 3
2 2 3
3 2 3
5 4 4
6 4 4
7 2 2
7 4 4
0 0 0
1
2
3
4
5
6
7
| 0 2 3 0 0 0 0
0 3 0 0 0 0 0
0 3 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 4 0 0 0
0 0 0 4 0 0 0
0 2 0 4 0 0 0
|
答案是25，然而我的解法第一次是：
1
2
3
4
5
6
7
| 0 0 3 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 2 0 0 0 0 0
|
得20，第二次得23。
实际上是第一次：
1
2
3
4
5
6
7
| 0 0 3 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 4 0 0 0
0 0 0 4 0 0 0
0 0 0 0 0 0 0
|
第二次全吞完，得25。
所以得用四维dp做。
四维dp
直接上代码吧：
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
| #include<bits/stdc++.h>
using ll = long long;
using namespace std;
int dp[11][11][11][11];
int a[11][11];
void solve(){
int n; cin >> n;
while(1) {
int x, y, z;
cin >> x >> y >> z;
if (x == 0 && y == 0 && z == 0) {
break;
}
else {
a[x][y] = z;
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
for (int p = 1; p <= n; ++p) {
for (int q = 1; q <= n; ++q) {
dp[i][j][p][q] = max(max(dp[i-1][j][p-1][q], dp[i-1][j][p][q-1]), max(dp[i][j-1][p-1][q], dp[i][j-1][p][q-1])) + a[i][j] + a[p][q];
if (i == p && j == q) dp[i][j][p][q] -= a[i][j];
}
}
}
}
cout << dp[n][n][n][n] << endl;
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int _=1;
while(_--)
solve();
return 0;
}
|