题解 P3146 【[USACO16OPEN]248】

· · 题解

可以看出是区间DP

对于每一个区间记录的是能构成的最大值

因为是相邻的区间，思路是枚举每一个分界点

即i从2枚举到n

然后枚举i前的点j和i后的点k

就构成了两个相邻的区间f_{j,i-1}和f_{i,k}

如果$f_{j,i-1}=f_{i,k} 然后试几组数据会发现答案不对 这是因为前面的区间可以被后面更新的区间更新 举个例子 #### $3\;2\;2\;1

显然最优解是先合并两个2再用合出来的3与原来的3合并

为了解决这一问题，多次循环就好了

保证后面合出来的区间能与前面的区间合并

代码：

# include<iostream>
# include<cstdio>
# include<cstring>
using namespace std;
int n;
int f[301][301];
void fre()
{
    //freopen("248.in","r",stdin);
    //freopen("248.out","w",stdout);
}
int main()
{
    fre();
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
      scanf("%d",&f[i][i]);
    for(int l=1;l<=10;l++)
      for(int i=2;i<=n;i++)
        for(int j=i-1;j>=1;j--)
          for(int k=i;k<=n;k++)
            if(f[j][i-1]==f[i][k])
            f[j][k]=max(f[j][k],f[j][i-1]+1);
    int maxn=0;
    for(int i=1;i<=n;i++)
      for(int j=i;j<=n;j++)
        maxn=max(maxn,f[i][j]);
    printf("%d",maxn);
    return 0;
}