洛谷P3147 262144

题目

此题数据范围小的话可以用区间\(DP\)，但是该题目的数据范围并不能用区间DP来求解，因此我们考虑优化\(DP\)。

每个数的生成一定是由这两个区间

考虑区间DP的弊端是并不知道每个数生成的区间是什么，所以需要枚举，而这枚举的时间就浪费了。因此考虑以区间信息为状态，在找到区间信息里比较好转移的状态，可得：

状态：\(dp[i][j]\)表示能形成\(i\)这个数的连续区间在以\(j\)为左端点时的右端点。

方程：\(dp[i][j]=dp[i-1][dp[i-1][j]]\)意思就是\(i\)这个数形成的连续区间以\(j\)为左端点时的右端点等于\(i-1\)这个数以\(j\)为左端点的右端点为左端点的右端点。

然后再注意注意枚举顺序就可以得出代码了。

#include <bits/stdc++.h>
using namespace std;
int n, maxn = 0, data[1000010], dp[61][1000100];
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        int a;
        scanf("%d", &a);
        dp[a][i] = i + 1;//d[i][j]表示i这个数在j为左端点的右端点是什么。
    }

    for (int i = 1; i <= 58; i++)
        for (int j = 1; j <= n; j++)
        {
            dp [i] [j] = max(dp[i][j], dp [i - 1] [ dp [i - 1] [j] ]);//dp[i][j]可以由之前的转移过来
            if (dp[i][j]) //如果i这个数存在右端点。
                maxn = max(maxn, i);
        }
    printf("%d", maxn);
    return 0;
}