BZOJ 4576: [Usaco2016 Open]262144

Description

一个序列,每次可以将两个相同的数合成一个数,价值+1,求最后最大价值 \(n \leqslant 262144\)

Sol

DP.

这道题是 BZOJ 4580: [Usaco2016 Open]248 加强版.

做248的那个区间DP其实很多方案都是0,而且一个区间中只有一个合法的数字.

然后就是 一个区间合成一个数的方案的这个数字是固定的.

\(f[i][j]\) 表示以 \(i\) 结尾是否能合成 \(j\),同时记录一下转移位置,每次向前找前一个指针就可以了.

复杂度 \(O(nm)\)

Code

/**************************************************************

    Problem: 4576

    User: BeiYu

    Language: C++

    Result: Accepted

    Time:1208 ms

    Memory:79368 kb

****************************************************************/

#include <cstdio>

#include <iostream>

using namespace std;

const int N = 263005;

const int M = 60;

int n,ans,a[N];

bool f[N][M];int g[N][M];

inline int in(int x=0){ scanf("%d",&x);return x; }

int main(){

    n=in();

    for(int i=1;i<=n;i++) a[i]=in();

    for(int i=1,p;i<=n;i++){

        p=i-1,f[i][a[i]]=1,g[i][a[i]]=i;

        ans=max(ans,a[i]);

        for(int j=a[i];j<M;j++){

            if(f[p][j]) f[i][j+1]=1,g[i][j+1]=g[p][j],p=g[p][j]-1,ans=max(ans,j+1);

            else break;

        }

    }

//  for(int i=1;i<=n;i++) for(int j=1;j<6;j++) cout<<i<<" "<<j<<" "<<f[i][j]<<" "<<g[i][j]<<endl;

    cout<<ans<<endl;

    return 0;

}