萌萌题：一道结合了观察性质的线性 dp。

观察

我们先考虑极端情况：所有数相同，所有数降序排列两种情况。

对于所有数相同的情况，我们发现，最终可以合并出来的区间，最多只有 \(n \log n\) 个。

怎么证明？考虑固定右端点，那么我们想要合并出一个点，就得选 \(2^k\) 个数出来，这就有 \(\log n\) 次选择方式。总的来说就是有 \(n \log n\) 种选数方式了。

所有数降序排列是多少？我们只需要将最后两个元素合并，然后继续往前面合并即可。总体来说有 \(n\) 个。

dp 设计

这题还有个很重要的观察：对于固定了右端点的时候，假设我们要让这个数增加 \(v\)，那么合并的方案（区间）一定是唯一的。这就启发了我们可以设计一个 dp，定义 \(dp_{i,j}\) 表示让元素 \(i\) 增加 \(j\) 后，合并到的区间的左端点的前一个数是哪里。

为什么要前一个数？其实你不要这前一个数其实也可以做。只不过我这样设计来讲比较好写转移的代码。

接下来就是很显然的转移，假设目前合并到的区间的左端点的前一个数为 \(now\)，要增加 \(v\)：

然后记录一下合法状态就好了。

这样写对吗？实际上假了。这是我赛时的做法，当时误以为一个数最多增量只可能是 \(\log n\)。实际上降序排列就能把增量卡到 \(n\)。

那么开大小为 \(n\) 的增量可不可以？直接开肯定不行，会 MLE，但是动态开不就行了？根据前面的观察，我们最多只有 \(n \log n\) 个合法区间，那么每个数的增量也最多只有 \(n \log n\) 个，我们用 vector 模拟动态开 dp 数组的过程，这道题就 AC 了。

注意，当某个区间无法继续合并下去的时候，要立刻 break，才能保证复杂度正确，否则会退化为平方级别。

时间复杂度为 \(O(n\log n)\)。

代码

#include <bits/stdc++.h>
#define fi first
#define se second
#define lc (p<<1)
#define rc ((p<<1)|1)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pi;
int n,a[100005],ans=0;
vector<int>dp[100005];
int main()
{
    freopen("cute.in","r",stdin);
    freopen("cute.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        dp[i].emplace_back(i-1);
        for(int j=1;j<=100000;j++)
        {
            int now=dp[i][j-1];
            int ta=a[now];
            int dt=a[i]+j-1-ta;
            if(dt>=0&&dt<dp[now].size())dp[i].emplace_back(dp[now][dt]);
            else break;
        }
    }
    for(int i=1;i<=n;i++)ans=max(ans,a[i]+int(dp[i].size())-1);
    cout<<ans<<endl;
    return 0;
}