hdu 6357 Hills And Valleys

hdu 6357 Hills And Valleys"/>

hdu 6357 Hills And Valleys

Problem Description
Tauren has an integer sequence A of length n (1-based). He wants you to invert an interval [l,r] (1≤l≤r≤n) of A (i.e. replace Al,Al+1,⋯,Ar with Ar,Ar−1,⋯,Al) to maximize the length of the longest non-decreasing subsequence of A. Find that maximal length and any inverting way to accomplish that mission.
A non-decreasing subsequence of A with length m could be represented as Ax1,Ax2,⋯,Axm with 1 ≤ x1< x2<⋯< xm≤ n and Ax1 ≤ Ax2≤⋯≤Axm.

Input
The first line contains one integer T, indicating the number of test cases.
The following lines describe all the test cases. For each test case:
The first line contains one integer n.
The second line contains n integers A1,A2,⋯,An without any space.
1≤T≤100, 1≤n≤105, 0≤Ai≤9 (i=1,2,⋯,n).
It is guaranteed that the sum of n in all test cases does not exceed 2⋅105.

Output
For each test case, print three space-separated integers m,l and r in one line, where m indicates the maximal length and [l,r] indicates the relevant interval to invert.

Sample Input
2
9
864852302
9
203258468

Sample Output
5 1 8
6 1 2

Hint

In the first example, 864852302 after inverting [1, 8] is 032584682, one of the longest non-decreasing subsequences of which is 03588.
In the second example, 203258468 after inverting [1, 2] is 023258468, one of the longest non-decreasing subsequences of which is 023588.

题意：任意反转一段，问可以得到的最长非递减序列。
做法：dp，首先解释一下状态，对于0-i这一段，假如反转了x到i这一段，
得到了1->(x-1),i->x,(i+1)->n这样一个串s，那么对于反转x到i+1这一段，得到一个1->(x-1),(i+1).i->x,(i+2)->n，这样一个串t，可以发现对于这两个串，对s和t，如果先不考虑最后一段，可以发现前两段中t串只是在某个位置比s串多了一个值而已，那么只需要考虑t串种用到这个值时的情况，如果用不到这个值，s串能得到的最长串，必定也是t串的最长串。假设dp[j][m][k]代表第一段值从0到j，第二段的值选取从m到k时的最长长度，那么可以用n^3从i的得到i+1是的dp，由上面的结论，我们可以发现，如果不考虑第三段，那么（i+1）只会对s串种，第一段最大值不超过A(i+1)并且第二段最小值不小于A(i+1)的这些状态会造成影响，所以对于所有的dp[j][m][k]（i位置的dp）(j <= A(i+1)&&m >= A(i+1))这样的状态用来更新dp[j][A(i+1)][k]（i+1位置的），就可以了得到i+1的dp了，对于i+1位置其他的状态，得到的结果图i位置dp是相同的，这个是很明显正确的，然后需要在开一个数组来保存每个状态得到最大值时，是从哪个位置反转过来的，不过要注意-1这个状态代表当前段得到最大值不需要反转的意思。最后一段需要预处理解决。

#include<bits/stdc++.h>
using namespace std;
int dp[11][11][11];
int ls[11][11][11];
const int N= 1e5+7;
int cnt[N][11];
int cns[N][11];
char st[N];
int main(){int T;cin >> T;while(T--){int len;scanf("%d",&len);scanf("%s",st);memset(cnt,0,sizeof(cnt));memset(dp,0,sizeof(dp));memset(ls,-1,sizeof(ls));memset(cns,0,sizeof(cns));for(int i = len-1;i >= 0;i --){int x= st[i]-'0';int mx = 0;for(int j= 9;j >= x;j --){cnt[i][j] = cnt[i+1][j];mx = max(mx,cnt[i+1][j]);}cnt[i][x] = mx+1;for(int j = x-1;j >= 0;j --){cnt[i][j] = cnt[i+1][j];}/*for(int j= 0;j <= 9;j ++){cout << i << ' '<< j << ' '<< cnt[i][j] << endl;}*/}cns[0][st[0]-'0'] = 1;for(int i = 1;i < len;i ++){int x= st[i]-'0';int mx  = 0;for(int j = 0;j <= x;j ++){cns[i][j] = cns[i-1][j];mx = max(mx,cns[i][j]);}cns[i][x] = mx+1;for(int j = x+1;j <= 9;j ++) cns[i][j] = cns[i-1][j];}int ans = 0;int tmp = -1;int nl = -1;for(int i = 0;i < len;i ++){int x= st[i]-'0';for(int k =x;k <= 9;k ++){for(int j = 0;j <= x;j ++){int mx = dp[j][x][k];for(int m = x;m <= k;m ++){if(dp[j][m][k]+1 > mx){//if(i == 4) cout << j << ' '<< m << ' '<< k << ' ' << dp[j][m][k] << ' '<< mx << ' '<< ls[j][m][k] << endl;if(ls[j][m][k] == -1){ls[j][x][k] = i;}else{ls[j][x][k] = ls[j][m][k];}mx = dp[j][m][k]+1;}}dp[j][x][k] = mx;}}//cout <<"!!!" << i << ' '<< dp[4][5][9] << ' '<<ls[4][5][9] << endl;for(int j = x;j <= 9;j ++){for(int k = j;k <= 9;k ++){if(dp[x][j][k] <= cns[i][x]){dp[x][j][k] = cns[i][x];ls[x][j][k] = -1;}}}int ret = 0;for(int m = 0;m <= 9;m ++){for(int j = 0;j <= m;j ++){for(int k = 0;k <= j;k ++){if(dp[k][j][m]+cnt[i+1][m] > ans) {ans = dp[k][j][m]+cnt[i+1][m];//cout << i << ' '<< ans << ' '<< ls[k][j][m] << endl;tmp = i;if(ls[k][j][m]!= -1)nl = ls[k][j][m];else nl = i;}}}}//if(i == 4) cout << dp[4][5][9] << ' ' << ls[4][5][9] << endl;//if(i == 5) cout << dp[4][5][9] << ' ' << ls[5][5][9] << endl;}printf("%d %d %d\n",ans,nl+1,tmp+1);}return 0;
}