hdu6357 Hills And Valleys （最长不下降子序列）

题目传送门

题意：

给你0~9的字符串，问你翻转哪个区间后使得其最长不下降子序列长度最长

思路：

因为字符是0~9，所以我们可以定义一个b数组来枚举L，R，

去和原来的字符串去求最长公共子序列长度，不断更新求最大值

然后在其中记录路径，不断回缩去求此时的L，R

代码：

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define N 100005

int n,b[];

char str[N];

int a[N],dp[N][],pre[N][];

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

        int ans=,ansl,ansr; scanf("%d %s",&n,str);

        for(int i=;i<n;i++) a[i+]=str[i]-'';

        for(int L=;L<=;L++)

        for(int R=L;R<=;R++){

            int tot=;

            for(int k=;k<=L;k++) b[++tot]=k;

            for(int k=R;k>=L;k--) b[++tot]=k;

            for(int k=R;k<=;k++) b[++tot]=k;

            //更新LCS

            for(int i=;i<=n;i++)

            {

                int t=;

                for(int j=;j<=tot;j++)

                {

                    if(dp[i-][j]>dp[i-][t]) t=j;

                    pre[i][j]=t;

                    dp[i][j]=dp[i-][t]+(a[i]==b[j]);

                }

            }

            for(int j=tot;j>=;j--)

            if(dp[n][j]>ans){

                ans=dp[n][j];

                int t=j,l=,r=;

                for(int i=n;i>=;i--){

                    if(!l&&t<=L+) l=i+;

                    if(!r&&t<=R+) r=i;

                    t=pre[i][t];

                }

                if(r==) r=l;

                ansl=l;ansr=r;

            }

        }

         printf("%d %d %d\n",ans,ansl,ansr);

    }

    return ;

}

参考博客：https://www.cnblogs.com/zquzjx/p/10333418.html