考虑一下n^2做法，f[i][j]表示从位置i往前j个位置，这些数能合成一个数，这个数的值为f[i][j]，这样的话初始化f[i][1]=1，然后向前找第一个一样的合起来即可，考虑优化，由于输入的数都<=40，所以所有的数都<=40+log n，f[i][j]表示第i个位置往前合成一个j合成到哪，这样就可以O(1)转移，复杂度O(n （40+log n)）
懒得写了无耻粘了一发commonc代码
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<ctime> #include<cmath> #include<algorithm> #include<iomanip> #include<vector> #include<map> #include<set> #include<bitset> #include<queue> #include<stack> using namespace std; #define MAXN 300010 #define MAXM 1010 #define INF 1000000000 #define MOD 1000000007 #define eps 1e-8 #define ll long long int a[MAXN][61]; int n; int main(){ int i,j,x,y; scanf("%d",&n); int ans=0; for(i=1;i<=n;i++){ scanf("%d",&x); a[i][x]=i; j=i-1; while(a[j][x]){ j=a[j][x]-1; a[i][++x]=j+1; } ans=max(ans,x); } printf("%d",ans); return 0; } /* */
