水题笔记_ Noip2000T4 + Noip2000T4改 + luogu1006 [DP]

信仰DP吧!

懵逼的 题目

改造前: 传送至 Codevs
改造后: 传送至 Vijos
传纸条: 传送至 Luogu

扯淡的 题解

先写改造前的就是4维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
//http://codevs.cn/problem/1043/
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#define MAXN (10 + 5)
using namespace std;
int n;
int a[MAXN][MAXN];
int f[MAXN][MAXN][MAXN][MAXN];
void dp();
int tmax(int, int, int, int);
int main()
{
scanf("%d", &n);
memset(a, 0, sizeof(a));
int srx, sry, srz;
do
{
scanf("%d%d%d", &srx, &sry, &srz);
if (!srx && !sry && !srz)
{
break;
}
a[srx][sry] = srz;
}
while(true);
dp();
printf("%d", f[n][n][n][n]);
return 0;
}
void dp()
{
memset(f, 0,sizeof(f));
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
for (int k = 1; k <= n; k++)
{
for (int kk = 1; kk <= n; kk++)
{
f[i][j][k][kk] = tmax(f[i][j - 1][k][kk - 1], f[i][j - 1][k - 1][kk], f[i - 1][j][k][kk - 1], f[i - 1][j][k - 1][kk]) + ((i == k && j == kk) ? (a[i][j]) : (a[i][j] + a[k][kk]));
//printf("%d %d %d %d: %d\n",i, j, k, kk, f[i][j][k][kk]);
}
}
}
}
}
int tmax(int x, int y, int xx, int yy)
{
x = max(x, y);
xx = max(xx, yy);
return max(x, xx);
}

改造后

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
70
71
72
73
//https://vijos.org/p/1143
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (20 + 5)
const int zx[8][4] = {{-1, -1, -1, -1}, {-1, 0, -1, -1}, {-1, 0, 0, -1}, {-1, 0, 0, 0}, {-1, 0, -1, 0}, {-1, -1, 0, -1}, {-1, -1, -1, 0}, {-1, -1, 0, 0}};
using namespace std;
int n;
int ans;
int f[MAXN + MAXN][MAXN][MAXN][MAXN];// j, k, kk 表示横着走的步数
int a[MAXN][MAXN];
int tmax(int, int, int, int);
void dp();
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
scanf("%d", &a[i][j]);
}
dp();
printf("%d", ans);
return 0;
}
void dp()
{
int maxstep = n << 1;
for (int i = 1; i < maxstep; i++)
{
for (int j = 1; j <= n; j++)
{
for (int k = 1; k <= n; k++)
{
for (int kk = 1; kk <= n; kk++)
{
f[i][j][k][kk] = tmax(i, j, k, kk);
}
}
}
}
ans = f[maxstep - 1][n][n][n];
}
int tmax(int step, int h1, int h2, int h3)
{
int maxp = 0;
for (int i = 0; i < 8; i++)
{
maxp = max(maxp, f[step + zx[i][0]][h1 + zx[i][1]][h2 + zx[i][2]][h3 + zx[i][3]]);
}
if (h1 == h2 && h1 == h3)
{
return maxp + a[h1][step - h1 + 1];
}
if (h1 == h2)
{
return maxp + a[h1][step - h1 + 1] + a[h3][step - h3 + 1];
}
if (h2 == h3)
{
return maxp + a[h1][step - h1 + 1] + a[h3][step - h3 + 1];
}
if (h1 == h3)
{
return maxp + a[h1][step - h1 + 1] + a[h2][step - h2 + 1];
}
if (h1 != h2 && h1 != h3 && h3 != h2)
{
return maxp + a[h1][step - h1 + 1] + a[h2][step - h2 + 1] + a[h3][step - h3 + 1];
}
}

传纸条

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
https://www.luogu.org/problem/show?pid=1006#sub
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (100 + 5)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
using namespace std;
int n;
int m;
int a[MAXN][MAXN];
int f[MAXN][MAXN][MAXN];// f[i][j][k] means it has used i steps && down j or k steps
inline int tmax(int, int, int, int);
int main()
{
memset(f, 0, sizeof(f));
scanf("%d%d", &m, &n);
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
scanf("%d", &a[i][j]);
}
}
for (int i = 1; i <= m + n - 3; i++)
{
for (int j = 0; j < min(n, i + 1); j++)
{
for (int k = j + 1; k < min(n, i + 1); k++)
{
if ((i - k) >= m || (i - j) >= m)
continue;
f[i][j][k] = max(f[i][j][k], f[i - 1][j][k] + a[i - j][j] + a[i - k][k]);
if (j > 0)
{
f[i][j][k] = max(f[i][j][k], f[i - 1][j - 1][k] + a[i - j][j] + a[i - k][k]);
}
if (k > 0)
{
f[i][j][k] = max(f[i][j][k], f[i - 1][j][k - 1] + a[i - j][j] + a[i - k][k]);
}
if (k > 0 && j > 0)
{
f[i][j][k] = max(f[i][j][k], f[i - 1][j - 1][k - 1] + a[i - j][j] + a[i - k][k]);
}
// printf("{i = %d; j = %d; k = %d}: %d\n", i, j, k, f[i][j][k]);
// f[i][j][k] = tmax(f[i - 1][j][k], f[i - 1][j][k - 1], f[i - 1][j - 1][k - 1], f[i - 1][j - 1][k - 1]) + a[j][i - j] + a[k][i - k];
}
}
}
printf("%d", f[n + m - 3][n - 2][n - 1]);
return 0;
}
inline int tmax(int a, int b, int c, int d)
{
a = max(a, b);
c = max(c, d);
return max(a, b);
}

By 啥都不会的 Cansult