题解 P3146 【[USACO16OPEN]248 G】

山蛙or山兔 · 2020-04-22 21:59:34 · 题解

看到了非常多不同的题解，果然这是个不错的题目，那我也发表一下自己的愚见吧。

用d[i][j]表示区间i~j能够合成的唯一数字k，如果不能合成一个数字，该值为-1.

易证：区间和唯一，所以不可能合成两个不同数字。

结果即所有可合成数字的最大值。

代码如下：

#include <iostream>
#include <cstring>
#include <cmath>
#define maxn 251
using namespace std;

int n,arr[maxn],d[maxn][maxn],ans,vis[maxn][maxn];

int dfs(int l,int r)
{
    if (vis[l][r]) return d[l][r];
    vis[l][r]=1;
    if (l==r) return d[l][r]=arr[l]; 
    for (int i=l;i<r;i++)
    {
        int x=dfs(l,i),y=dfs(i+1,r);
        if (x==y && x!=-1)
        {
            ans=max(ans,x+1);
            d[l][r]=x+1;
            break;  // 不可能合成出两种数字 
        }
    }
    return d[l][r];
}

int main()
{
    cin >> n;
    for (int i=1;i<=n;i++) cin >> arr[i];
    ans=0;
    memset(vis,0,sizeof(vis));
    memset(d,-1,sizeof(d));
    dfs(1,n);
    cout << ans << endl;
    return 0;
}// 好像忘记考虑一次都不能合成的情况了……