题解 P3146 【[USACO16OPEN]248】

· · 题解

看到楼上奇妙的状态我来补一个比较正常的……

我们可以用普通区间dp解：

f[i][j]表示区间 i-j 合并的最大值

转移：

若f[i][k]==f[k+1][j]-->f[i][j]=max(f[i][k]+1,f[i][j])

但要注意， 若f[i][k]!=f[k+1][j]，那么无法进行转移

一开始想的是：f[i][j]=max(f[i][j],max(f[i][k],f[k+1][j]));

但实际上是不可行的，因为只有相邻的才能合并，而上面的转移不能保证最大值在区间i-j的一端

这样我们对每段区间（包括区间[i,i]）取max即可

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=250;
int n,ans=0,f[N][N];
int main(){
    scanf("%d",&n);
    for (int i=1;i<=n;i++){
        scanf("%d",&f[i][i]);
        ans=max(ans,f[i][i]);
    }
    for (int i=n-1;i>=1;i--)
        for (int j=i+1;j<=n;j++){
            for (int k=i;k<j;k++)
                if (f[i][k]==f[k+1][j])
                    f[i][j]=max(f[i][j],f[i][k]+1);
            ans=max(ans,f[i][j]);
        }
    printf("%d",ans);
    return 0;
}