DDOSvoid's Blog

Luogu P3147 [USACO16OPEN]262144 P

发表于 分类于
本文字数： 659 阅读时长 ≈ 1 分钟

题目描述

https://www.luogu.com.cn/problem/P3147

挺有意思的类似倍增的dp

Solution

我们考虑首先如果合成一个数字，那么一定是用了一个区间的数字

如果数字都是1的话，那么我们知道左端点就能推出右端点

不是1的话，我们只需要将右端点存下来即可

我们令f[i][j]表示左端点是i，合成数字为j的右端点是f[i][j]

注意到能合成的最大数字为58，$2^{18}=262144$

总的时间复杂度为 $O(58n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <cstdio>
#define maxn 263000
#define maxm 60
using namespace std;

int n, a[maxn];

int f[maxn][maxm]; 

int ans; 
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), f[i][a[i]] = i;
    for (int j = 2; j < maxm; ++j)
        for (int i = 1; i <= n; ++i) {
            if (f[i][j - 1]) f[i][j] = f[f[i][j - 1] + 1][j - 1];
            if (f[i][j]) ans = j;
        }
    cout << ans << endl; 
    return 0;
}