P3147 [USACO16OPEN]262144 P

想到合并，自然就想到区间dp，一个被合成的数之前是一个区间，并且由两个数比它小 1 1 1 的区间合成。可麻烦的是，我们并不知道之前的两个区间长度各是多少。这道题不像一般的区间dp，明确地知道一个区间的答案由哪些区间转移。

在这道题，我们只知道要合成ii，就要找到两个紧接着它的两个 i − 1 i-1 i−1的区间。

既然如此，区间的长度是未知的，那我们设计状态的时候，把区间的长度设为转移的对象。

所以 f [ i ] [ j ] f[i][j] f[i][j]表示在数列上以j为起点，能合成数i的区间长度。若 f [ i ] [ j ] f[i][j] f[i][j]为0，说明不存在满足这个条件的区间，即在数列上以j为起点，无法合成数i。此题求解的是能合成的最大值，那就是满足 f [ i ] [ j ] > 0 f[i][j]>0 f[i][j]>0的最大的ii。

能和成它的区间只有接下去两个能合成i-1i−1的区间，它们的长度分别是 f [ i − 1 ] [ j ] f[i-1][j] f[i−1][j]和 f [ i − 1 ] [ j + f [ i − 1 ] [ j ] ] f[i-1][j+f[i-1][j]] f[i−1][j+f[i−1][j]]。从这里可以发现，第二个区间的起点位置由第一个区间的长度推导而来，这就是转移长度的原因。

显然，区间的长度是合成它两个区间的长度和，所以 f [ i ] [ j ] = f [ i − 1 ] [ j ] + f [ i − 1 ] [ j + f [ i − 1 ] [ j ] ] f[i][j]=f[i-1][j]+f[i-1][j+f[i-1][j]] f[i][j]=f[i−1][j]+f[i−1][j+f[i−1][j]]
但是，如果合成该区间的两个区间有一个为0，说明能合成该区间的区间就是不存在的，那么该区间也为0。

这道题用动态规划也有不同的做法，可以用 f [ i ] [ j ] f[i][j] f[i][j]表示在数列上以j为起点，能合成数i的区间的右端点。不过两种方法的储存的东西本质上是一样的。知道左端点位置的前提下，右端点位置、区间长度，知道其中一个可以推出另外一个。

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
#include<math.h>

#define ls (p<<1)
#define rs (p<<1|1)
#define mid (l+r)/2
#define over(i,s,t) for(register long long i=s;i<=t;++i)
#define lver(i,t,s) for(register long long i=t;i>=s;--i)

using namespace std;
typedef long long ll;//全用ll可能会MLE，ll比int占的内存大
const ll N=300000;
const ll INF=1e9+9;
const ll mod=2147483647;
const double EPS=1e-10;//-10次方约等于趋近为0
const double Pi=3.1415926535897;

ll f[100][N];
ll n,m,a;
int ans;
int main()
{
    scanf("%lld",&n);
    over(i,1,n)
    scanf("%lld",&a),f[a][i]=1;
    over(i,2,58)over(j,1,n)
    {
        if(!f[i][j])
        if(f[i-1][j]&&f[i-1][j+f[i-1][j]])
        f[i][j]=f[i-1][j]+f[i-1][j+f[i-1][j]];
        if(f[i][j])ans=i;
    }
    printf("%d\n",ans);return 0;
}

注：如果您通过本文,有(qi)用(guai)的知识增加了，请您点个赞再离开,如果不嫌弃的话,点个关注再走吧，日更博主每天在线答疑 ! 当然，也非常欢迎您能在讨论区指出此文的不足处，作者会及时对文章加以修正 !如果有任何问题，欢迎评论，非常乐意为您解答！( •̀ ω •́ )✧