题解之P3607

苏22 · 2021-11-11 13:52:51 · 题解

前言

前几天，老师让我们做题，结果，做这道，裂开。

正解

这道题是道区间 dp，但，难的一批，转移方程想到了就很简单。

首先，我们设一个数组 dp_{l,r,L,R}，表示从 l 到 r 的区间，值域为 L~R 的最大价值。

转移方程：我们先看看它不转换序列，最大价值，则为

dp[l][r][L][R]=max(dp[l][r][L+1][R],dp[l][r][L][R-1]);//把小值域的价值转换到大值域
dp[l][r][L][R]=max(dp[l][r][L][R],dp[l+1][r][L][R]+(a[l]==L));//向左扩展
dp[l][r][L][R]=max(dp[l][r][L][R],dp[l][r-1][L][R]+(a[r]==R));//向右扩展

接下来考虑序列转移后，转移方程怎么弄，既然要转换，也要是最长不下降子序列，则要判断，转换后，是否是最长不下降子序列，则为

dp[l][r][L][R]=max(dp[l][r][L][R],dp[l+1][r-1][L][R]+(a[l]==R)+(a[r]==L));//序列翻转后，最大价值 

这样的话，再初始化，就行了！！！！

AC代码

#include <algorithm>
#include <cstdio>
using namespace std;
int n, a[51], dp[51][51][51][51];
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        for (int L=1;L<=a[i];L++)
            for (int R=a[i];R<=50;R++)
                dp[i][i][L][R]=1;//初始化 
    }
    for (int len=2;len<=n;len++)//枚举区间长度 
    {
        for (int l=1,r=len;r<=n;l++,r++)//枚举起点和终点 
        {
            for (int llen=1;llen<=50;llen++)//枚举值域 
            {
                for (int L=1,R=llen;R<=50;L++,R++)//枚举值域起点和重点 
                {
                    dp[l][r][L][R]=max(dp[l][r][L+1][R],dp[l][r][L][R-1]);//把小值域的价值转换到大值域
                    dp[l][r][L][R]=max(dp[l][r][L][R],dp[l+1][r][L][R]+(a[l]==L));//向左扩展
                    dp[l][r][L][R]=max(dp[l][r][L][R],dp[l][r-1][L][R]+(a[r]==R));//向右扩展
                    dp[l][r][L][R]=max(dp[l][r][L][R],dp[l+1][r-1][L][R]+(a[l]==R)+(a[r]==L));//序列翻转后，最大价值 
                }
            }
        }
    }
    printf("%d",dp[1][n][1][50]);
    return 0;
}