题意

给出一个序列 A_1,A_2,\cdots,A_n（n\leq 10^5,0\leq A_i\leq 9），求将其翻转一个区间后的最长不降子序列的长度，以及要翻转的区间。

思路

由于 n 很大，枚举要翻转的区间的两个端点是不可行的。不妨考虑枚举区间的值域 [x,y]，那么我们可以由此构造出一个模式串0*1*...x*|y*(y-1)*...x*|y*(y+1)*...9*，其中 k* 表示匹配任意长度的字符 k 。我用 | 标识符将模式串分成了三段，其中中间的一段用于匹配翻转的区间。注意到此串中除了 x,y 个出现了两次，其他字符都只出现了一次，因此它的长度为 10+2=12。考虑 DP，设 f(i,j) 表示原序列中第 i 个数字匹配到模式串中第 j 个字符的最长匹配长度。不难得到转移：f(i,j)=\max\left(f(i, j-1),f(i-1,j)+[A_i=pattern_j]\right) 。这样就可以求得最长的长度了。

求区间时可以把 DP 的转移记录下去，从最终状态回溯，将 l,r 分别记为模式串匹配到相应位置时最小和最大的 i 即可。

代码

#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN=110000;
const int MAXM=15;
int n;
char s[MAXN], t[MAXN];
int f[MAXN][MAXM];
bool p[MAXN][MAXM];
int dp(int x, int y)
{
    int m=0;
    for (int i=0; i<=x; i++) t[++m]=i+'0';
    for (int i=y; i>=x; i--) t[++m]=i+'0';
    for (int i=y; i<=9; i++) t[++m]=i+'0';
    for (int i=1; i<=n; i++)
        for (int j=1; j<=m; j++)
            f[i][j]=max(f[i][j-1], f[i-1][j]+(s[i]==t[j]));
    return f[n][m];
}
pair<int, int> solve(int x, int y)
{
    int m=0, px, py;
    for (int i=0; i<=x; i++) t[++m]=i+'0';
    px=m+1;
    for (int i=y; i>=x; i--) t[++m]=i+'0';
    py=m;
    for (int i=y; i<=9; i++) t[++m]=i+'0';
    for (int i=1; i<=n; i++)
        for (int j=1; j<=m; j++)
        {
            int lhs=f[i][j-1], rhs=f[i-1][j]+(s[i]==t[j]);
            if (lhs>=rhs) f[i][j]=lhs, p[i][j]=0;
            else f[i][j]=rhs, p[i][j]=1;
        }
    int l=1, r=1;
    for (int i=n, j=m; i>0&&~j; i-=p[i][j], j-=!p[i][j])
    {
        if (j==px) l=i;
        if (r==1&&j==py) r=i;
    }
    return make_pair(l, r);
}
int main()
{
//  freopen("hdu6357.in", "r", stdin);
//  freopen("hdu6357.out", "w", stdout);
    int T;
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d%s", &n, s+1);
        int ans=0, sx, sy;
        for (int x=0; x<=9; x++)
            for  (int y=x; y<=9; y++)
            {
                int res=dp(x, y);
                if (res>ans) ans=res, sx=x, sy=y;
            }
        auto pos=solve(sx, sy);
        printf("%d %d %d\n", ans, pos.first, pos.second);
    }
    return 0;
}