：给一串由n个数字组成的字符串，选择其中一个区间进行翻转，要求翻转后该字符串的最长非降子序列长度最长，输出这个最长非降子序列的长度以及翻转的区间的左右端点
#includeusing namespace std;typedef long long ll;const int maxn = 100005;const int maxm = 22;int n, a[maxn], dp[maxn][maxm], b[maxm];int ans, ansl, ansr, l, r, cnt;int al[maxn][maxm], ar[maxn][maxm];char s[maxn]; int solve(){ for(int i = 0; i <= cnt; i++) dp[0][i] = 0; for(int i = 1; i <= n; i++) { for(int j = 1; j <= cnt; j++) { dp[i][j] = dp[i - 1][j]; al[i][j] = al[i - 1][j];//al记录翻转的左端点 ar[i][j] = ar[i - 1][j];//al记录翻转的左端点 if(a[i] == b[j]) { dp[i][j] = dp[i - 1][j] + 1; if(l == j && !al[i][j])//如果当前的j就是b开始翻转的左端点,更新记录 al[i][j] = i; if(r == j)//当前的j是b翻转的右端点,记录更新 ar[i][j] = i; } if(dp[i][j - 1] > dp[i][j])//如果答案有更新就要更新答案 { dp[i][j] = dp[i][j - 1]; al[i][j] = al[i][j - 1]; ar[i][j] = ar[i][j - 1]; } } } return dp[n][cnt];} int main(){ int t; scanf("%d", &t); while(t--) { scanf("%d%s", &n, s + 1); for(int i = 1; i <= n; i++) a[i] = s[i] - '0'; cnt = 0; for(int i = 0; i <= 9; i++) b[++cnt] = i; ansl = ansr = l = r = 1; ans = solve(); for(int i = 0; i <= 9; i++) //枚举翻转b数组的每一段 { for(int j = i + 1; j <= 9; j++) { cnt = 0; for(int k = 0; k <= i; k++) b[++cnt] = k; l = cnt+1;//左端点 for(int k = j; k >= i; k--)//只翻转i~j区间的数 b[++cnt] = k; r = cnt;//右端点 for(int k = j; k <= 9; k++) b[++cnt] = k; /* for(int i=1; i<=cnt; i++) printf("%d ",b[i]); printf("\n");*/ int tmp = solve(); if(ans < tmp && al[n][cnt] && ar[n][cnt])//不断更新答案 { ans = tmp; ansl = al[n][cnt], ansr = ar[n][cnt]; } } } printf("%d %d %d\n", ans, ansl, ansr); } return 0;}