题目概述

给出长度为 $n$ 的数字串，求最长非降子序列的长度，允许翻转一个区间 $[l,r]$ 。

解题报告

因为数字串，所以我们可以利用数值定义状态来快速转移，而翻转考虑三段DP：

$f[i][j]$ 表示前 $i$ 个以 $j$ 这个数结尾的方案数，$g[i][j]$ 表示从 $i$ 开始以 $j$ 这个数作为开头的方案数，而 $h[i][j][k]$ 表示翻转区间的值域为 $[i,j]$ ，以 $k$ 这个数结尾的方案数。

那么我们先预处理 $f,g$ ，然后从 $1$ 到 $n$ 做DP：

1. $h[l][r][j]+1\to h[l][r][a[i]],j\ge a[i]$ 。
2. $f[i-1][j]+1\to h[j][a[i]][a[i]],j\le a[i]$ 。
3. $h[l][r][j]+g[i+1][r]\to ans$ 。

至于翻转方案，记录 $pos[l][r][j]$ 表示 $h[l][r][j]$ 的左端点，更新答案的时候 $l=pos[l][r][j],r=i$ 。

示例程序

感谢学长度教全程陪同写代码&调试（雾）。

#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=100000;

int te,n,a[maxn+5],MAX[10],f[maxn+5][10],g[maxn+5][10],h[10][10][10],pos[10][10][10],ans,A,B;

inline char getdig() {char ch=getchar();while (!isdigit(ch)) ch=getchar();return ch;}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    for (scanf("%d",&te);te;te--){
        scanf("%d",&n);for (int i=1;i<=n;i++) a[i]=getdig()-'0';
        memset(f,0,sizeof(f));for (int i=0;i<10;i++) MAX[i]=0;
        for (int i=1;i<=n;i++){
            for (int j=0;j<10;j++) f[i][j]=MAX[j];
            for (int j=0;j<=a[i];j++)
                f[i][a[i]]=max(f[i][a[i]],MAX[j]+1);
            MAX[a[i]]=max(MAX[a[i]],f[i][a[i]]);
        }
        memset(g,0,sizeof(f));for (int i=0;i<10;i++) MAX[i]=0;
        for (int i=n;i;i--){
            for (int j=0;j<10;j++) g[i][j]=MAX[j];
            for (int j=9;j>=a[i];j--)
                g[i][a[i]]=max(g[i][a[i]],MAX[j]+1);
            MAX[a[i]]=max(MAX[a[i]],g[i][a[i]]);
        }
        memset(h,0,sizeof(h));ans=0;
        for (int i=1;i<=n;i++){
            for (int l=0;l<=a[i];l++)
                for (int r=a[i];r<10;r++)
                    for (int j=a[i];j<=r;j++)
                        if (h[l][r][j]&&h[l][r][j]+1>h[l][r][a[i]])
                            h[l][r][a[i]]=h[l][r][j]+1,pos[l][r][a[i]]=pos[l][r][j];
            for (int j=0;j<=a[i];j++)
                if (f[i-1][j]+1>h[j][a[i]][a[i]])
                    h[j][a[i]][a[i]]=f[i-1][j]+1,pos[j][a[i]][a[i]]=i;
            for (int l=0;l<10;l++)
                for (int r=l;r<10;r++)
                    for (int j=l;j<=r;j++)
                        if (h[l][r][j]+g[i+1][r]>ans)
                            ans=h[l][r][j]+g[i+1][r],A=pos[l][r][j],B=i;
        }
        printf("%d %d %d\n",ans,A,B);
    }
    return 0;
}