题解 P3146 【[USACO16OPEN]248】

Manjusaka丶梦寒 · 2018-08-23 14:33:26 · 题解

区间dp，这次设计的状态和一般的有一定的差异。

这次我们定义dp[i][j]表示[i,j]的可以合并出来最大取值，而不是合并区间[i,j]的最大取值。

同样的我们枚举区间长度，枚举左端点，求出右端点。

枚举i到j之间的每一个分割点，判断两点之间是否可以合并，取价值更高的答案。

Question 1:其他的点不需要更新，为什么？

这就要看我们设计的状态了，我们定义的是区间[i,j]可以合并出来的最大值，答案唯一，当然不能用其位置的更新了。

Question 2:答案是什么？

注意这里的答案不一定是dp[1][n],你想当我们计算区间[1,n]时所有的dp[i][k]!=dp[k+1][j]那么区间[1,n]的答案为0，答案在之前已经得出，所以我们在过程中记录一下就好了。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <map>
using namespace std;
#define LL long long
#define mod int(1e9+7)
int n,a[250],dp[250][250],ans;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        dp[i][i]=a[i];  //初始化dp数组 
    }
    for(int len=2;len<=n;len++)
    {
        for(int i=1;i<=n;i++)
        {
            int j=i+len-1;
            if(j>n)break;   //超出长度限制 
            for(int s=i;s<j;s++)
            {
                if(dp[i][s]==dp[s+1][j])dp[i][j]=max(dp[i][j],dp[i][s]+1);
            }
            ans=max(dp[i][j],ans);  //记录答案 
        }
    }
    printf("%d",ans);
}