水题笔记_ luogu1430 序列取数 + codevs3002 石子归并3 [DP × 优化]

最近搞DP遇到几个优化上的问题…
优化大法好$n ^ 3$变$n ^ 2$

懵逼的 题目

  1. 传送至 Luogu
  2. 传送至 Codevs

扯淡的 题解

  1. 首先是先打一个n ^ 3暴力好了…结果WAWAWA…
    发现两边的k重叠了…就是说左区间和右区间都包含了k…GG
    然后终于把暴力改对了…愉快的改正解
    WAWAWA…
    怀疑人生
    把DP的优化全都搜了…感觉并不合适(因为加上还是WA)…
    然后看了看题解(我错了)…发现我一开始的优化思路是对的…WTF???
    但是没有考虑到最小值是有两种情况, 一个是从左边的最小, 一个是从右边的最小…
    终于A了…

  2. 看了看四边形不等式才做的…
    当前的最优转移点k一定在[le, ri - 1][le + 1][ri]两个子区间的最优转移之间, 并不会证明
    感觉四边形不等式用起来很简单啊(flag), 就是不会证啊
    然后WAWAWA…
    发现其实是可以取到s[le + 1][ri]的 (其实这种优化直接加<=就好了吧反正时间也超不了太多, 换来正确性和简单是值得的)…然后我写的是k < s[le + 1][ri]…GG
    改过来, A了

沙茶的 代码

  1. 记录区间的最值来优化(并不知道叫什么名字…)

AC代码

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (1000 + 5)
#define INF (10000000)
using namespace std;
int n;
int sum[MAXN][MAXN];
int ls[MAXN][MAXN];
int rs[MAXN][MAXN];
int a[MAXN];
int f[MAXN][MAXN];
int fr[MAXN];
void init();
void dp();
inline void getint(int*);
int main()
{
int t;
getint(&t);
while (t--)
{
init();
dp();
printf("%d\n", f[1][n]);
}
return 0;
}
void init()
{
getint(&n);
for (register int i = 1; i <= n; i++)
{
getint(a + i);
fr[i] = fr[i - 1] + a[i];
f[i][i] = a[i];
rs[i][i] = ls[i][i] = a[i];
}

}
void dp()
{
for (register int i = 1; i <= n; i++)
{
for (register int j = 1; j <= n - i + 1; j++)
{
int le = j;
int ri = j + i;
f[le][ri] = max(fr[ri] - fr[le - 1], max(fr[ri] - fr[le - 1] - ls[le][ri - 1], fr[ri] - fr[le - 1] - rs[le + 1][ri]));
ls[le][ri] = min(ls[le][ri - 1], f[le][ri]);
rs[le][ri] = min(rs[le + 1][ri], f[le][ri]);
}
}
}
inline void getint(int* re)
{
*re = 0;
char x = 0;
int zf = 1;
while (x < '0' || x > '9')
{
x = getchar();
if (x == '-')
{
zf = -1;
}
}
while (x >= '0' && x <= '9')
{
*re = ((*re) << 1) + ((*re) << 3) + x - '0';
x = getchar();
}
(*re) *= zf;
}
/*
2
1 -1
2 1 2
*/

/*
1
5
-5 6 -3 2 -4
*/

/*
1
5
-1 -1 -1 -1 -1
*/

k重复: 爆零的暴力

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (1000 + 5)
#define INF (10000000)
using namespace std;
int n;
int sum[MAXN][MAXN];
int a[MAXN];
int f[MAXN][MAXN];
int fr[MAXN];
void init();
void dp();
int main()
{
int t;
scanf("%d", &t);
while (t--)
{
memset(fr, 0, sizeof(fr));
memset(sum, 0, sizeof(sum));
memset(f, 0, sizeof(f));
memset(a, 0, sizeof(a));
init();
dp();
printf("%d\n", f[1][n]);
}
return 0;
}
void init()
{
scanf("%d", &n);
for (int i = 0; i <= n; i++)
{
for (int j = 0; j <= n; j++)
{
f[i][j] = -INF;
}
}
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
fr[i] = fr[i - 1] + a[i];
f[i][i] = a[i];
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= i; j++)
{
sum[j][i] = fr[i] - fr[j - 1];
}
}
}
void dp()
{
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n - i + 1; j++)
{
int le = j;
int ri = j + i;
f[le][ri] = sum[le][ri];
for (int k = le + 1; k < ri; k++)
{
if (f[k][ri] != -INF && f[le][k] != -INF)
f[le][ri] = max(f[le][ri], max(sum[le][ri] - f[k][ri], sum[le][ri] - f[le][k]));
}
}
}
}
/*
2
1 -1
2 1 2
*/

/*
1
5
-5 6 -3 2 -4
*/

/*
1
5
-1 -1 -1 -1 -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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (1000 + 5)
#define INF (10000000)
using namespace std;
int n;
int sum[MAXN][MAXN];
int a[MAXN];
int f[MAXN][MAXN];
int fr[MAXN];
void init();
void dp();
int main()
{
int t;
scanf("%d", &t);
while (t--)
{
memset(fr, 0, sizeof(fr));
memset(sum, 0, sizeof(sum));
memset(f, 0, sizeof(f));
memset(a, 0, sizeof(a));
init();
dp();
printf("%d\n", f[1][n]);
}
return 0;
}
void init()
{
scanf("%d", &n);
for (int i = 0; i <= n; i++)
{
for (int j = i; j <= n; j++)
{
f[i][j] = -INF;
}
}
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
fr[i] = fr[i - 1] + a[i];
f[i][i] = a[i];
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= i; j++)
{
sum[j][i] = fr[i] - fr[j - 1];
}
}
}
void dp()
{
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n - i + 1; j++)
{
int le = j;
int ri = j + i;
f[le][ri] = sum[le][ri];
for (int k = le; k < ri; k++)
{
f[le][ri] = max(f[le][ri], max(sum[le][ri] - f[k + 1][ri], sum[le][ri] - f[le][k]));
}
}
}
}
/*
2
1 -1
2 1 2
*/

/*
1
5
-5 6 -3 2 -4
*/

/*
1
5
-1 -1 -1 -1 -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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (1000 + 5)
#define INF (10000000)
using namespace std;
int n;
int sum[MAXN][MAXN];
int a[MAXN];
int f[MAXN][MAXN];
int minf[MAXN][MAXN];
int fr[MAXN];
void init();
void dp();
int main()
{
int t;
scanf("%d", &t);
while (t--)
{
memset(fr, 0, sizeof(fr));
memset(sum, 0, sizeof(sum));
memset(f, 0, sizeof(f));
memset(a, 0, sizeof(a));
init();
dp();
printf("%d\n", f[1][n]);
}
return 0;
}
void init()
{
scanf("%d", &n);
for (int i = 0; i <= n; i++)
{
for (int j = i; j <= n; j++)
{
f[i][j] = -INF;
}
}
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
fr[i] = fr[i - 1] + a[i];
minf[i][i] = f[i][i] = a[i];
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= i; j++)
{
sum[j][i] = fr[i] - fr[j - 1];
}
}
}
void dp()
{
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n - i + 1; j++)
{
int le = j;
int ri = j + i;
minf[le][ri] = min(minf[le + 1][ri], minf[le][ri - 1]);
f[le][ri] = max(sum[le][ri], max(sum[le][ri] - minf[le][ri], sum[le][ri] - minf[le][ri]));
minf[le][ri] = min(minf[le][ri], f[le][ri]);
}
}
}
/*
2
1 -1
2 1 2
*/

/*
1
5
-5 6 -3 2 -4
*/

/*
1
5
-1 -1 -1 -1 -1
*/
  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
62
#include <cstdio>
#include <cstring>
#define MAXN (3000 + 5)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define INF (0x7fffffff)

int n;
int a[MAXN];
int s[MAXN][MAXN];
int f[MAXN][MAXN];
int fr[MAXN];

int ans = INF;

void dp();
int main()
{
memset(f, 0x7f, sizeof(f));
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
fr[i] = a[i] + fr[i - 1];
s[i][i] = i;
f[i][i] = 0;
}
dp();
printf("%d", f[1][n]);
return 0;
}
void dp()
{
int le;
int ri;
for (int i = 1; i <= n; i++)
{
for (int j = 1; i + j <= n; j++)
{
le = j;
ri = i + j;
for (int k = s[le][ri - 1]; k <= s[le + 1][ri]; k++)
{
if (f[le][ri] > (f[le][k] + f[k + 1][ri] + fr[ri] - fr[le - 1]))
{
f[le][ri] = f[le][k] + f[k + 1][ri] + fr[ri] - fr[le - 1];
s[le][ri] = k;
}
}
}
}
}

/*
4
4 5 9 4
*/

/*
4
4 1 1 4
*/

By Noip药丸的 Cansultc

Only my RAILGUN can shoot it.必ず

我永远爱御坂9982