题解 P3146 【[USACO16OPEN]248】

Jiang_zi_chuan · 2018-12-26 17:46:05 · 题解

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

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

我的转移方程：

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

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

如图：

最后，附上代码

#include <bits/stdc++.h>
using namespace std;
int N, x, f[60][262200], ans;
int main(){
    scanf("%d", &N);
    for(int i = 1; i <= N; i++)
        scanf("%d", &x), f[x][i] = i;
    for(int i = 2; i <= 58; i++)
        for(int j = 1; j <= N; j++){
            if(!f[i][j] && f[i - 1][j]) 
                f[i][j] = f[i - 1][f[i - 1][j] + 1];
            if(f[i][j])ans = i;
        }
    printf("%d", ans);
    return 0;
}