Bessie喜欢在手机上下游戏玩，然而她蹄子太大，很难在小小的手机屏幕上面操作。
她被她最近玩的一款游戏迷住了，游戏一开始有n个正整数，(2<=n<=262144)，范围在1-40。在一步中，贝西可以选相邻的两个相同的数，然后合并成一个比原来的大一的数（例如两个7合并成一个8)，目标是使得最大的数最大，请帮助Bessie来求最大值。
分析题意
首先我们知道这个游戏叫做2048，对于262144这个看起来就不一般的数字来一个log2，log2262144=18
所以答案的范围一定在40+18=58以内
所以就可以开始乱搞优化了
类倍增
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn=1e6+5; 4 const int INF=1e9+7; 5 int n,ans,dp[262145][60],t; 6 template <class t>void red(t &x) 7 { 8 x=0; 9 int w=1; 10 char ch=getchar(); 11 while(ch<‘0‘||ch>‘9‘) 12 { 13 if(ch==‘-‘) 14 w=-1; 15 ch=getchar(); 16 } 17 while(ch>=‘0‘&&ch<=‘9‘) 18 { 19 x=(x<<3)+(x<<1)+ch-‘0‘; 20 ch=getchar(); 21 } 22 x*=w; 23 } 24 void input() 25 { 26 freopen("input.txt","r",stdin); 27 } 28 void read() 29 { 30 red(n); 31 for(int i=1;i<=n;++i) 32 { 33 red(t); 34 dp[i][t]=i+1; 35 } 36 } 37 void work() 38 { 39 for(int j=2;j<=58;++j) 40 for(int i=1;i<=n;++i) 41 { 42 if(!dp[i][j]) 43 dp[i][j]=dp[dp[i][j-1]][j-1]; 44 if(dp[i][j]) 45 ans=j; 46 } 47 printf("%d",ans); 48 } 49 int main() 50 { 51 //input(); 52 read(); 53 work(); 54 return 0; 55 }
原文：https://www.cnblogs.com/Achensy/p/10804621.html
