HDU 6049 - Sdjpx Is Happy|2017 Multi-University Training Contest 2

花门楼前见秋草，岂能贫贱相看老。这篇文章主要讲述HDU 6049 - Sdjpx Is Happy|2017 Multi-University Training Contest 2相关的知识，希望能为你提供帮助。
思路来源于 FXXL - -
一个比较奇怪的地方就是第三步可以不做，也就是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剪枝 */ #include < bits/stdc++.h> using 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); } }

【HDU 6049 - Sdjpx Is Happy|2017 Multi-University Training Contest 2】