[USACO16OPEN]262144

标签：动态规划 区间DP

---

题目描述

Bessie喜欢在手机上下游戏玩（……），然而她蹄子太大，很难在小小的手机屏幕上面操作。
她被她最近玩的一款游戏迷住了，游戏一开始有n个正整数，(2<=n<=262144)，范围在1-40。在一步中，贝西可以选相邻的两个相同的数，然后合并成一个比原来的大一的数（例如两个7合并成一个8)，目标是使得最大的数最大，请帮助Bessie来求最大值。

输入输出格式

输入格式

The first line of input contains N, and the next N lines give the sequence of N numbers at the start of the game.

输出格式

Please output the largest integer Bessie can generate.

样例

输入样例#1：
4
1
1
1
2

输出样例#1：
3

题解

那么此题和[USACO16OPEN]248题面是一样的，唯一不同的是这数据量达到了20w，因此肯定不能用原来n^3的算法了。
不过有一条性质依旧没变：两段区间如果要合并，那么必须满足两段区间分别合并得到的数字相同。
并且分析此题的数据，可以发现，最后合并的数字绝对不会超过58。因此，我们是可以记录能合并到的数字的状态的。
于是我们设f[i][j]表示以j为起点,能合并到i数字的终点。（这神仙状态设计…实在是巧妙）
然后我们可以用一种倍增的思想进行转移：
$$f[i][j]=f[i-1][f[i-1][j]]$$
于是我们只需要第一层枚举能合成的数字，第二层枚举数组长度就可以了，复杂度为$O（58*n）$

代码

#include<bits/stdc++.h>
#define N 300010
#define M 60
using namespace std;

int n, x, ans = -1;
int f[M][N];

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++)
    {
        scanf("%d", &x);
        f[x][i] = i + 1;
        ans = max(ans, x);
    }
    for(int i = 2; i <= 58; i ++)
        for(int j = 1; j <= n; j ++)
        {
            if(f[i][j]) continue;
            f[i][j] = f[i - 1][f[i - 1][j]];
            if(f[i][j] > 0) ans = max(ans, i);
        }
    printf("%d", ans);
    return 0;
} 

心得

这倍增的思想着实巧妙啊，多多积累。