【题解】[Usaco2016 Open]262144 Dp BZOJ – 4576

题目戳我_(:з」∠)_

一开始想到了类似分治的做法，但还是 Naive 了

设我要合并出一个数值 $i$，被合并的区间左端点位置为 $j$，区间右端点的位置 $+1$等于 $f[i][j]$

这里的位置指的是在初始数组中的下标

比如对于初始数组的第 $i$个元素 $a[i]$，$f[a[i]][i]$就等于 $i+1$

那么可以写出转移方程：

$$f[i][j] = f[i – 1][f[i – 1][j]]$$

就是说当前我要合成 $i$，且从 $j$开始合成。

那我可以先从 $j$开始合成一个 $i – 1$，再从合成出这个 $i – 1$的区间终止位置开始再合成出一个 $i-1$，这样拿它俩合并就得到了一个 $i$了，而 $f[i][j]$也就等于第二次合成 $i-1$的终止位置（+1）了

丢代码就跑真刺激

#include <bits/stdc++.h>

#define DS (60)
#define NS (262150)

using namespace std;

template<typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

int n, f[DS][NS], ans;

int main(int argc, char const* argv[])
{
    IN(n);
    for (int i = 1, a; i <= n; i += 1) IN(a), f[a][i] = i + 1;
    for (int i = 2; i <= 58; i += 1)
        for (int j = 1; j <= n; j += 1)
        {
            if (!f[i][j]) f[i][j] = f[i - 1][f[i - 1][j]];
            if (f[i][j]) ans = i;
        }
    printf("%d\n", ans);
    return 0;
}