6357.
自己感觉这是个好题，应该是经典题目，所以半路选手补了这道字符串的动态规划题目。
题意就是给你一个串，翻转任意区间一次，求最长的非下降子序列。
一看题面写的0≤Ai≤9 (i=1,2,⋯,n).就知道肯定有点东西，只要这么写，肯定就是有某个神奇的操作可以解决这道题目。
比赛的时候脑壳都要炸了也没想出来，补题的时候懂了，我可以定义一个b串为0123456789，这肯定是递增的，所以我翻转b的某个区间，然后去和a匹配，因为我把b再翻转回来，还是递增的。
当然了，因为是非严格的递增子序列，有相等的情况，所以相等的时候判断一下，直接+1就可以了。然后枚举一下b的翻转区间就可以了。因为还要输出翻转的区间，所以在dp的时候，用个数组分别保存一下l，r端点就可以了。其他的没什么。
感觉这种思路还是很值得思考的，不处理a，通过其他的操作间接处理a，以后写题要多想想，也写过类似思路的，通过其他的操作间接得到答案，但是一打比赛就没脑子，mdzz，为什么我这么菜༼༎ຶᴗ༎ຶ༽
参考了其他人的题解写出来的。
首先官方题解:
然后别人的博客:HDU6357——Hills And Valleys
代码:
//1008-6357-非严格递增子序列(最长非下降子序列)-字符串+dp-区间翻转，r找最长非递减子序列，好题哇
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<deque>
#include<iomanip>
#include<list>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
using namespace std;
typedef long long ll; const double PI=acos(-1.0);
const double eps=1e-;
const ll mod=1e9+;
const int inf=0x3f3f3f3f;
const int maxn=1e5+;
const int maxm=+;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); int n,a[maxn],dp[maxn][maxm],b[maxm];
int ans,L,R,l,r,h;
int al[maxn][maxm],ar[maxn][maxm]; int solve()
{
for(int i=;i<=h;i++)
dp[][i]=;//初始化
for(int i=;i<=n;i++){//a和b匹配
for(int j=;j<=h;j++){
dp[i][j]=dp[i-][j];
al[i][j]=al[i-][j];//记录左端点
ar[i][j]=ar[i-][j];//记录右端点
if(a[i]==b[j]){//如果有相等的情况，+1
dp[i][j]=dp[i-][j]+;
if(l==j&&!al[i][j])//如果当前的j就是b开始翻转的左端点,更新记录
al[i][j]=i;
if(r==j)//右端点
ar[i][j]=i;
}
if(dp[i][j-]>dp[i][j]){//更新答案
dp[i][j]=dp[i][j-];
al[i][j]=al[i][j-];
ar[i][j]=ar[i][j-];
}
}
}
return dp[n][h];
} char s[maxn]; int main()
{
int t;
scanf("%d",&t);
while(t--){
scanf("%d%s",&n,s+);
for(int i=;i<=n;i++)
a[i]=s[i]-'';
h=;
for(int i=;i<=;i++)
b[++h]=i;
L=R=l=r=;
ans=solve();
for(int i=;i<=;i++){
for(int j=i+;j<=;j++){
h=;
for(int k=;k<=i;k++)
b[++h]=k;//翻转区间的左部分不变
l=h+;
for(int k=j;k>=i;k--)//要翻转的区间把数字翻转
b[++h]=k;
r=h;
for(int k=j;k<=;k++)//反转区间的右部分不变
b[++h]=k;
int tmp=solve();
if(ans<tmp&&al[n][h]&&ar[n][h]){//更新结果
ans=tmp;
L=al[n][h];
R=ar[n][h];
}
}
}
printf("%d %d %d\n",ans,L,R);
}
}
溜了溜了，滚去补数据结构了。