思路来源于 - -
一个比较奇怪的地方就是第三步可以不做，也就是ans至少为1，听说场内有提问的，然后 admin 说可以不做- - (wa的我心烦)
/*HDU 6049 - Sdjpx Is Happy [ 枚举,剪枝 ] | 2017 Multi-University Training Contest 2题意： 长度为N的排列 N <= 3000 排序分三个步骤： 1.原数组分为不相交的K段 2.每段都独立排序 3.选择其中两段swap 问按步骤能成功排序的K能取到的最大是多少分析： 先预处理出任意段的最小值和最大值 再处理出任意[l,r]段最多能分成多少段有效段，用f[i,j]表示 所谓的有效段首先满足 Max[i,j]-Min[i,j] = j-i 再满足其中每段依此递增，即前一段的最大值 == 后一段的最小值-1 设需要交换的前一段为[i, j] 后一段为[k, t] 枚举i,j，则 t = Max[i][j]，再枚举k，更新答案 虽然枚举复杂度大，但可以剪枝 比如要求：f[i,j] > 0 && i 如果不为 1 则 Min[1,i-1] = 1, Max[1, i-1] = i-1 类似的对k, t剪枝*/#includeusing namespace std;const int N = 3005;int Max[N][N], Min[N][N];int f[N][N];int t, n;int a[N], last[N];void init(){ memset(f, 0, sizeof(f)); int i, j, k; for (i = 1; i <= n; i++) Max[i][i] = Min[i][i] = a[i]; for (k = 2; k <= n; k++) for (i = 1; i+k-1 <= n; i++) { j = i+k-1; Max[i][j] = max(Max[i+1][j], Max[i][i]); Min[i][j] = min(Min[i+1][j], Min[i][i]); } for (i = 1; i <= n; i++) f[i][i] = 1, last[i] = i; for (k = 2; k <= n; k++) for (i = 1; i+k-1 <= n; i++) { j = i+k-1; if (Max[i][j] - Min[i][j] != j-i) continue; if (Min[i][last[i]] != Min[i][j]) f[i][j] = 1; else f[i][j] = f[i][last[i]] + 1; last[i] = j; }}int ans;void solve(){ ans = f[1][n]; for (int i = 1; i <= n; i++) { if ( i != 1 && (!f[1][i-1] || Max[1][i-1] != i-1)) continue; for (int j = i; j <= n; j++) { if (!f[i][j]) continue; int t = Max[i][j]; if (t != n && (!f[t+1][n] || Min[t+1][n] != t+1 || Max[t+1][n] != n)) continue; for (int k = t; k > j; k--) { if (!f[k][t] || Min[k][t] != i ) continue; if (k > j+1) { if (!f[j+1][k-1] || Max[k][t] != Min[j+1][k-1]-1 || Min[i][j] != Max[j+1][k-1]+1) continue; } else { if (Max[k][t] != Min[i][j]-1) continue; } ans = max(ans, f[1][i-1] + 2 + f[j+1][k-1] + f[t+1][n]); } } }}int main(){ scanf("%d", &t); while (t--) { scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", a+i); init(); solve(); printf("%d\n", ans); }}