题解 P3146 【[USACO16OPEN]248】

· · 题解

三分钟读题，五分钟AC。

裸的区间DP

f[i][j]代表合并区间[i,j]得到的最大值。

转移

当f[i][k] == f[k + 1][j]时，f[i][j] = max(f[i][j] , f[i][k] + 1);

进行O(n^3)的转移即可，数据范围比较小，没有必要四边形不等式优化。

Code: 
#include <bits/stdc++.h>

using namespace std;

const int N = 300;
int n , a[N];
int f[N][N];
int ans;

int main () {
    scanf("%d" , &n);
    for(int i = 1 ; i <= n; ++ i) scanf("%d" , a + i);
    for(int i = 1 ; i <= n ; ++ i) f[i][i] = a[i];

    for(int len = 2 ; len <= n ; ++ len) {
        for(int i = 1 ; i <= n - len + 1 ; ++ i) {
            int j = i + len - 1;
            for(int k = i; k <= j - 1; ++ 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;
}