洛谷P3147 [USACO16OPEN]262144
2048 合并
题意 每次可以把相邻的两个相同的数字合并， 如x 和 x 合并之后 值就是 x+1
求最终最大能够合并到的数字大小
题解 一种 做法类似倍增 动归 递推
f[ i ][ j ] 表示 从第 i -- f[ i ][ j ]-1 位 这几位的和是 j
然后就可以递推 或者说动归了，因为要相同j是由前后两个相同 j-1合并而来的，
f[ i ][ j ] = f[ f[ i ][ j-1 ] ][ j-1 ] 合并当然是从小到大合并的
因为先把小的合并了，大的合并机会才会更多嘛，另一个理由就是根据公式，
在算 j 时 需要事先算出 i-1 才行
1 #include <cstdio> 2 #include <cstring> 3 #include <cstdlib> 4 #include <cmath> 5 #include <algorithm> 6 #include <string> 7 #include <iostream> 8 #include <iomanip> 9 using namespace std ; 10 11 const int maxn = 300011,maxm = 61; 12 13 int n,ans ; 14 int a[maxn],f[maxn][maxm-1] ; 15 16 inline int read() 17 { 18 char ch = getchar() ; 19 int x = 0,f = 1 ; 20 while(ch<'0'||ch>'9') { if(ch=='-') f = -1 ; ch = getchar() ; } 21 while(ch>='0'&&ch<='9') { x = x*10 + ch-48 ; ch = getchar() ; } 22 return x*f ; 23 } 24 25 int main() 26 { 27 n = read() ; 28 for(int i=1;i<=n;i++ ) a[ i ] = read() ; 29 for(int j=1;j<maxm;j++) 30 { 31 for(int i=1;i<=n;i++) 32 { 33 if(a[ i ]==j) f[ i ][ j ] = i+1 ; 34 else f[ i ][ j ] = f[ f[ i ][ j-1 ] ][j-1] ; 35 if(f[ i ][ j ]) ans=max(ans,j) ; 36 } 37 } 38 printf("%d ",ans) ; 39 return 0 ; 40 }