题意：给你一个序列， 可以翻转一次区间 [l, r] 求最大 非递减的 序列长度。
题解：枚举翻转区间，然后匹配。
如果不翻转区间， 那么就相当于用b[] = {0,1,2,3,...,7,8,9} 来匹配原序列， 可以重复匹配， 求最长的长度。
现在我们假设翻转b的 [3,5] 那么 新的b的序列就为 b[] = {0,1,2,3,5,4,3,5,6,7,8,9} 来匹配a序列，求最长的长度。
新的bn的序列最多就是C(10,2)次。
dp[n][m] 代表的是 匹配到 a序列的第n位 b序列的第m位他最多匹配了多少个数。
dp[n][m] = max(dp[n][m-1], dp[n-1][m] + (a[n] == b[m]);
开新的数组记录匹配 dp[n][m] 的翻转区间的开始点与结束点。 我们需要当翻转区间的开始点和结束点都出现过才会记录答案。
因为翻转b的情况都枚举完了， 那么最优解的情况肯定会出现在自己的翻转区间的情况下。
代码：
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout); 4 #define LL long long 5 #define ULL unsigned LL 6 #define fi first 7 #define se second 8 #define pb push_back 9 #define lson l,m,rt<<1 10 #define rson m+1,r,rt<<1|1 11 #define max3(a,b,c) max(a,max(b,c)) 12 #define min3(a,b,c) min(a,min(b,c)) 13 typedef pair<int,int> pll; 14 const int inf = 0x3f3f3f3f; 15 const LL INF = 0x3f3f3f3f3f3f3f3f; 16 const LL mod = (int)1e9+7; 17 const int N = 1e5 + 100; 18 char s[N]; 19 int b[N], dp[N][15], al[N][15], ar[N][15]; 20 int n, m, ans, l, r, ll, rr; 21 int solve(){ 22 for(int i = 0; i < 10; i++) dp[0][i] = 0; 23 for(int i = 1; i <= n; i++){ 24 for(int j = 1; j <= m; j++){ 25 dp[i][j] = dp[i-1][j]; 26 al[i][j] = al[i-1][j]; 27 ar[i][j] = ar[i-1][j]; 28 if(s[i]-'0' == b[j]){ 29 dp[i][j] = dp[i - 1][j] + 1; 30 if(ll == j && !al[i][j]) al[i][j] = i; 31 if(rr == j) ar[i][j] = i; 32 } 33 if(dp[i][j-1] > dp[i][j]){ 34 dp[i][j] = dp[i][j-1]; 35 al[i][j] = al[i][j-1]; 36 ar[i][j] = ar[i][j-1]; 37 } 38 } 39 } 40 return dp[n][m]; 41 } 42 43 int main(){ 44 int T; 45 scanf("%d", &T); 46 while(T--){ 47 scanf("%d", &n); 48 scanf("%s", s+1); 49 m = 0; 50 for(int i = 0; i <= 9; i++) b[++m] = i; 51 l = r = 1; ans = solve(); 52 for(int i = 0; i <= 9; i++){ 53 for(int j = i+1; j <= 9; j++){ 54 m = 0; 55 for(int k = 0; k <= i; k++) b[++m] = k; 56 ll = m + 1; 57 for(int k = j; k >= i; k--) b[++m] = k; 58 rr = m; 59 for(int k = j; k <= 9; k++) b[++m] = k; 60 int tmp = solve(); 61 if(ans < dp[n][m] && al[n][m] && ar[n][m]){ 62 ans = dp[n][m]; 63 l = al[n][m], r = ar[n][m]; 64 } 65 } 66 } 67 printf("%d %d %d ", ans, l, r); 68 } 69 70 return 0; 71 }