USACO16OPEN_248&&USACO16OPEN_262144_KEY

题目传送门

这道题比较水，设f[i][j]表示i~j区间合并的最大值。

#include <cstdio>

#define max(a,b) a>b?a:b

using namespace std;

int N,x,f[][],ans;

int main(){

    scanf("%d",&N);for(int i=;i<=N;i++)scanf("%d",&x),f[i][i]=x,ans=max(ans,x);

        for(int i=N-;i>;i--)

            for(int j=i+;j<=N;j++)

                for(int k=i;k<j;k++)

                    if(f[i][k]==f[k+][j]){

                        f[i][j]=max(f[i][k]+,f[i][j]);

                        ans=max(ans,f[i][j]);

                    }

    printf("%d",ans);

    return ;

}

水

但这道题目还有扩大数据范围后的做法：

题目传送门

仔细观察方程：

f[i][j]=max(f[i][k]+,f[i][j]);

我们设的是i~j区间的最大值，这里有个巧妙的转化，设f[i][j]为j开始最大值达到i的右边界。

#include <cstdio>

using namespace std;

int N,x,f[][],ans;

int main(){

    scanf("%d",&N);for(int i=;i<=N;i++)scanf("%d",&x),f[x][i]=i;

    for(int i=;i<=;i++)

        for(int j=;j<=N;j++){

            if(!f[i][j]&&f[i-][j])f[i][j]=f[i-][f[i-][j]+];

            if(f[i][j])ans=i;

        }

    printf("%d",ans);

    return ;

}

数据扩大