248

发表于 更新于 分类于

Problem’s Website

  • 248

    Solution

  • 这道题是一道区间dp模板题，区间dp，根据名称，我们可以得出是在区间内做dp，一般设$f[i][j]$为左端点为$i$,右端点为$j$是的某一状态，对于这道题来说，$f[i][j]$为把$i$到$j$合并的最大值。

  • 我们首先从大到小枚举左右端点，如果相邻两个相等，就可以合并，所以伪代码为

    1
    2
    3
    4
    5
    6
    for i (n-1) ~ 1
    	for j (i+1) ~ n
        	for k i ~ j
                if(f[i][k] == f[k+1][j])
                	f[i][j] = max(~, f[i][k]+1);
                ans = max(~, f[i][j]);

    答案即为ans.

    Code

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #define gc getchar()
    #define pc(x) putchar(x)
    #define re register
    const int Maxn = 300;
    inline int sc() {
        int xx = 0, ff = 1; char cch = gc;
        while(!isdigit(cch)) {
            if(cch == '-') ff = -1; cch = gc;
        }
        while(isdigit(cch)) {
            xx = (xx << 1) + (xx << 3) + (cch ^ '0'); cch = gc;
        }
        return xx * ff;
    }
    inline void out(int x) {
        if(x < 0) pc('-'), x = -x;
        if(x >= 10)
            out(x / 10);
        pc(x % 10 + '0');
    }
    int n, ans;
    int f[Maxn][Maxn];
    int main() {
    	n = sc();
    	for(re int i = 1; i <= n; ++i)
    		f[i][i] = sc(), ans = std :: max(ans, f[i][i]);
    	for(re int i = n - 1; i >= 1; --i)
    		for(re int j = i + 1; j <= n; ++j)
    			for(re int k = i; k < j; k++) {
    				if(f[i][k] == f[k + 1][j]) {
    					f[i][j] = std :: max(f[i][j], f[i][k] + 1);	
    				}
    				ans = std :: max(ans, f[i][j]);
    			}
    	out(ans), pc('\n');
        return 0;
    }
    // Coded by dy.

rp++