题目大意:给定一个长度为n的数列.初始时数列中每个元素都不大于40,你可以在其上进行若干次操作.在一次操作中，你会选出相邻且相等的两个元素,把它们合并成一个元素,新的元素值为旧元素值+1.请你找出,怎样的一系列操作可以让数列中的最大值变得尽可能地大?这个最大值是多少?
一开始往数据结构上想,想错了,正解是dp
luogu有原题248G
对于弱化版的,直接\(O(N^2)\)就行
如下为我自己推的dp
状态:设\(f_i\)表示在前i个数中,所能合成的最大的数字,其中第i个位置参不参与合成都可以
转移:
\(f_i =
f_{i-1}\)即第i个数字不参与合成,那么答案就是直接前i-1的
\(f_i
=...\)把第i个数字压入栈,然后不断往前更新,合并.最后对栈里的元素取max
代码如下:
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
| int n, top;
int a[N], f[N], sta[N];
inline int func(int x)
{
int i, res(0);
top = 0, memset(sta, 0, sizeof sta);
sta[++ top] = a[x];
for (i = x - 1; i >= 1; -- i)
{
if (a[i] == sta[top])
{
++ sta[top];
while (sta[top] == sta[top - 1]) sta[top --] = 0, ++ sta[top];
}
else sta[++ top] = a[i];
}
for (i = 1; i <= top; ++ i) res = max(res, sta[i]);
return res;
}
signed main()
{
int i; n = read();
for (i = 1; i <= n; ++ i) a[i] = read();
f[1] = a[1];
for (i = 2; i <= n; ++ i)
{
f[i] = f[i - 1];
f[i] = max(f[i], func(i));
}
put(f[n]);
return 0;
}
|
再来考虑可以\(O(N\times K)\)算的
状态很奇妙:\(f_{i,j}\)表示到第i个位置,能否合成j这个数字,如果可以合成,那么他的后继是谁
转移:
\(f_{i,j-1}\;and\;f_{f_{i,j-1},j-1}\)都存在的话
\(f_{i,j} =
f_{f_{i,j-1},j-1}\)(这里记录的是"后继",也可以记录"前驱")
然后转移的时候不断更新ans
代码如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| #include <bits/stdc++.h>
const int N = 3e5;
int n, res;
int f[N][66];
signed main()
{
int i, j; n = read();
for (i = 1; i <= n; ++ i) f[i][read()] = i + 1;
for (j = 2; j <= 60; ++ j)
{
for (i = 1; i <= n; ++ i)
{
if (f[i][j - 1] && f[f[i][j - 1]][j - 1])
{
f[i][j] = f[f[i][j - 1]][j - 1], res = j;
}
}
}
put(res);
return 0;
}
|