一、题目链接

P3147 [USACO16OPEN]262144 P

二、题目大意

给定一个1×n1\times n1×n的序列aaa，每次可以合并相邻两个（数值范围1∼401\sim 401∼40），问序列中出现的最大数字的值最大是多少。合并后的数值并非加倍而是+1+1+1，例如222与222合并后的数值为333。

数据范围：2≤n≤262144,1≤a[i]≤402\leq n\leq 262144,1\leq a[i]\leq402≤n≤262144,1≤a[i]≤40。

三、题目分析

1. 首先这道题目一眼看过去，很明显是一个区间DPDPDP的题目，而且状态转移方程很容易想。

2. 设dp[i][j]dp[i][j]dp[i][j]为将i∼ji\sim ji∼j全部合并的最大值，设置区间长度从小到大进行状态转移。当dp[i][k]==dp[k+1][j]dp[i][k]==dp[k+1][j]dp[i][k]==dp[k+1][j]时，dp[i][j]=max(dp[i][j],dp[i][k]+1)dp[i][j]=max(dp[i][j],dp[i][k]+1)dp[i][j]=max(dp[i][j],dp[i][k]+1)

3. 此方案的时间复杂度为O(n3)O(n^3)O(n3)，显然不足以完成此题目，但是可以通过此题目的弱化版：P3146 [USACO16OPEN]248 G。此题的数据范围为2≤n≤2482\leq n\leq2482≤n≤248。

4. 至此我们仍有一个很关键的信息没有利用上，那就是nnn这个奇怪的数据范围。可以发现262144=218262144=2^{18}262144=218，所以最终的答案不会超过40+18=5840+18=5840+18=58。

5. 我们首先分析一下合并的结果，对于区间(i,j)(i,j)(i,j)来说，如果能够将它们全部合并，那么最终的合并结果一定是唯一的。

6. 接下来分析一下区间DPDPDP的具体过程。如果(i,j)(i,j)(i,j)可以合并出xxx，那么若k>jk>jk>j，(i,k)(i,k)(i,k)的合并最大值是否能为xxx？显然是不能的，所以对于合并结果xxx和区间开头iii来说，有且只有一个jjj与之对应。由于xxx的数量级远小于jjj，所以如果我们遍历iii和jjj那么复杂度显然不如遍历iii和xxx。

7. 据此我们可以列出状态转移方程式：dp[x][i]=dp[x−1][dp[x−1][i]+1]dp[x][i]=dp[x-1][dp[x-1][i]+1]dp[x][i]=dp[x−1][dp[x−1][i]+1]，我们仅需遍历xxx和iii，且xxx的最大值根据444可知，仅为585858。故而时间复杂度仅为O(58×n)O(58\times n)O(58×n)，符合题目要求。

四、正解程序：

#include 
#include 
#include 
#include using namespace std;
typedef int ll;
const ll maxn=300000;
ll n,dp[60][maxn],num[maxn];
int main()
{cin>>n;for(ll i=1;i<=n;i++){cin>>num[i];dp[num[i]][i]=i;}ll ans=0;for(ll x=1;x<=58;x++){for(ll i=1;i<=n;i++){if(!dp[x][i] && dp[x-1][i]!=0)dp[x][i]=dp[x-1][dp[x-1][i]+1];if(dp[x][i])ans=x;}}cout<