题目传送门:P3147

前言

这题是区间 dp\text {dp} 绿题, dp\text{dp} 还是有点难想的。

一开始觉得和合并石子差不多,后来看了看N262144N\le 262144,就不会了,于是去看了题解。

dp[i][j]dp[i][j]表示以 jj 为左端点合并出 ii 时的右端点。

一看到这个式子的时候,觉得挺奇怪的。

这个用到了类似于倍增的思想,如果所有数都是 4040 的话,最大合出来的数是 5858 。所以就是 58n58n 的复杂度。

妙啊!妙啊!

递推式

dp[i][j]=dp[i1][dp[i1][j]]dp[i][j]=dp[i-1][dp[i-1][j]]

解释:dp[i1][j]dp[i-1][j]表示 jj 为左端点合并出 i1i-1 时的右端点, dp[i1][dp[i1][j]]dp[i-1][dp[i-1][j]] 就是 22i1i-1 合起来,这个原理和合并石子差不多的。

初始化

For(i,1,n) dp[q=read()][i]=i+1;//以i为左端点合并出 q 时的右端点是i+1

代码

int main() {
    read(n);
    For(i,1,n) read(q),f[q][i]=i+1;
    For(i,1,58)
    For(j,1,n){
        if(!f[i][j]) f[i][j]=f[i-1][f[i-1][j]];
        if(f[i][j]) ans=i;
    }
    write(ans);
}