题解 P3147 【[USACO16OPEN]262144】

# 动态规划 其实这题很简单，但是我就是看了题解。。。 这篇题解的思路和其他$dalao$的大同小异，但是这篇主要解释了$58$这个神奇的数字，以及状态转移方程的意思 **** # 状态 我们定义$f[i][j]$,里面存的值是左端点为$j$，能合并出$i$这个数字的右端点的位置 那么状态转移方程如下: $$f[i][j]=f[i-1][f[i-1][j]]$$ 为什么呢？ 其实这就有点倍增的味道了，我们首先（没有图，自行脑补或者参考其他人的题解$qwq$） 我们先在脑海中画一个数轴$qwq$ 然后最左边的一个点位置为$j$ 那么我们可以求出$f[i-1][j]$，也就是从$j$往后一直合并到哪个位置，可以最终合并出$i-1$，这个位置其实就是$f[i-1][j]$ 那么我们接下来呢？ 我们从这个位置继续向后，看看到哪个位置又能合并出一个$i-1$，那么找到这个点，其实就是$f[i-1][f[i-1][j]]$,我们合并到这里的时候，就会合并出两个相邻的$i-1$，那么不就可以合并出一个$i$了吗？ 所以，状态转移就是$$f[i][j]=f[i-1][f[i-1][j]]$$ #### 接下来是美滋滋的代码时间~~~ ~~~cpp #include<iostream> #include<cstdio> #define N 61 #define M 270007 using namespace std; int n,ans; int f[N][M]; int main() { scanf("%d",&n); for(int i=1;i<=n;++i) { int in; scanf("%d",&in); f[in][i]=i+1; } for(int i=2;i<=58;++i)//58????? for(int j=1;j<=n;++j) { if(!f[i][j]) f[i][j]=f[i-1][f[i-1][j]]; if(f[i][j]) ans=i; } printf("%d",ans); } ~~~ ### 那么上面这个神奇的$58$呢？ 其实就跟数据范围有关 我们看到$2≤N≤262144$，而我们像倍增一样合并，那么因为$2^{18}=262144$ 而数字的大小在$1-40$之间，那么产生的数最多也就是$40+18=58$啦 **** ### 如果有错误，请私信我或者评论留言~~（而我不会看）~~