题解 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]]

接下来是美滋滋的代码时间~~~

#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啦

如果有错误，请私信我或者评论留言（而我不会看）