题解 P3146 【[USACO16OPEN]248】

· · 题解

关于解法楼下大佬们已经给出了许多种做法，不过这里我想在讨论一下关于f[i][j]的含义。

f[i][j]表示为区间i-j能合成的最大值，转移方程:

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

我起初并不太理解这样的设计方案，因为我可以构造这样一组数据:

6

1 3 1 1 3 1

那么f[1][3]=3, f[4][6]=3; 按照定义f[1][6]=4;当然这肯定是不合法的。所以我觉得f[i][j]这样定义比较合理（或者说容易理解）:f[i][j]表示i-j合成为一个数字的值,无法合成为一个数字则f[i][j]=-1; 此时如果能合成一个数字的话也肯定是最大值。所以并不违反最优情况的求解，如果不能合成的话表示这段区间无法和其他区间合并，所以设置-1表示一种不合法情况。

这里可以设置一组HACK数据，大家可以尝试一下：

12

1 2 1 2 1 2 1 2 1 2 1 2

答案是2，但是如果如果不设置不合法标志的话许多人答案可能为4

#include<bits/stdc++.h>
#define N 510
using namespace std;

int n, x, ans = -1;
int f[N][N];

int main()
{
    scanf("%d", &n);
    memset(f, 0, sizeof(f));
    for(int i = 1; i <= n; i ++)
    {
        scanf("%d", &f[i][i]);
        ans = max(ans, f[i][i]);
    }
    for(int len = 1; len <= n; len ++)
        for(int i = 1; i <= n - len + 1; i ++)
        {
            int j = i + len - 1;
            for(int k = i; k < j; k ++)
                if(f[i][k] == f[k + 1][j] && f[i][k] != -1)
                   f[i][j] = max(f[i][j], f[i][k] + 1);
            ans = max(ans, f[i][j]); 
        }
    printf("%d", ans); 
    return 0;
}