自动搬运

查看原文

来自洛谷，原作者为

	苏22 GD人 o(￣▽￣)ブ

搬运于2025-08-24 21:50:41，当前版本为作者最后更新于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;
}