又一道区间DP的题 -- P3146 [USACO16OPEN]248

https://www.luogu.org/problemnew/show/P3146

一道区间dp的题,以区间长度为阶段;

但由于要处理相邻的问题,就变得有点麻烦;

最开始想了一个我知道有漏洞的方程

if(f[i][k] != f[k + 1][j]) f[i][j] = max(f[i][k],f[k + 1][j]);
else f[i][j] = max(f[i][j],f[i][k] + 1);

可能f[i][k] = f[i][j],但他们可合并的并未相邻;

可以这样

#include <bits/stdc++.h>
#define read read()
#define up(i,l,r) for(int i = (l);i <=(r); i++)
using namespace std;
int read
{
    int x = 0; char ch = getchar();
    while(ch < 48 || ch > 57) ch = getchar();
    while(ch >= 48 && ch <= 57) {x = 10 * x + ch - 48; ch = getchar();}
    return x;
}
const int N = 250;
int n,a[N],f[N][N],ans;
int main()
{
    freopen("248.in","r",stdin);
    n = read;
    up(i,1,n) a[i] = read;
    up(i,1,n) {f[i][i] = a[i];ans = max(ans,f[i][i]);printf("[%d,%d] : %d
",i,i,f[i][i]);}
    up(L,2,n)
        up(i,1,(n - L + 1))
            {
                int j = i + L - 1;
                f[i][j] = 0;
                up(k,i,j - 1)
                {
                    //if(f[i][k] != f[k + 1][j])
                    //f[i][j] = max(f[i][k],f[k + 1][j]);
                    //else
                    if(f[i][k] == f[k + 1][j])
                    f[i][j] = max(f[i][j],f[i][k] + 1);
                }
                ans = max(f[i][j],ans);
                //printf("[%d,%d] : %d
",i,j,f[i][j]);
            }
    printf("%d",ans);
    //printf("%d",f[1][n]);
    return 0;
}

区间长度由小到大,并且只合并相邻的,更新答案;

保证了能输出最大值;

又一道区间DP的题 -- P3146 [USACO16OPEN]248

相关推荐