题目连接
题意
存在一个
1−n
全排列数列 A。将数列 A 划分成不为空的k块，并将每一块按升序排序。可以选取其中的两块进行交换，但此操作至多进行一次。求完成操作后将数列 A 排列成升序状态的最大 k 是多少。
分析
以
A[i...j]
表示数列
ai,ai+1,......,aj
。设
f[i][j]
为分块排序再组合后保证
A[i...j]
连续且上升的前提下，
A[i...j]
至多能分成几块。如果不进行交换操作，那么
f[1][n]
就是所求答案。
f[i][j]
可以通过枚举
i
，然后不断枚举 j ，显然只有
j−i=max{ak∣i≤k≤j}−min{ak∣i≤k≤j}
时，才符合组成一块的条件。记录一个变量
cur
为离
j
最近的满足 f[i][cur]≠0 的情况，于是判断
min{ak∣i≤k≤j}<min{ak∣i≤k≤cur}
否成立就能判断
A[cur+1...j]
是否能独立成为一块了。现在考虑交换的情况，枚举交换的第一块的起点为
i
和终点为 j 。要进行交换，必须能够划分为成至少一个块，即
f[i][j]≠0
；如果
i==1
则要求
min{ak∣i≤k≤j}≠1
,否则要求
f[1][i−1]≠0
且
min{at∣i≤t≤j}≠1
。设
k=max{at∣i≤t≤j}
,如果
k≠n
，必然要求
f[k+1][n]≠0
且
max{at∣i≤t≤j}==n
，条件均成立的情况下再枚举第二段的起点
t
，在 f[t][k]≠0 且
min{ap∣t≤p≤k}==i
时，形成交换的可行方案，计算此时的答案。详细实现过程参考代码。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define MAXN 3030
int mn[MAXN][
13];
int mx[MAXN][
13];
int a[MAXN];
int f[MAXN][MAXN];
int lg2[MAXN];
int n;
int formin(
int l,
int r){
int k=lg2[r-l+
1];
return min(mn[l][k],mn[r-(
1<<k)+
1][k]);
}
int formax(
int l,
int r){
int k=lg2[r-l+
1];
return max(mx[l][k],mx[r-(
1<<k)+
1][k]);
}
void init(){
memset(f,
0,
sizeof(f));
for(
int i=
2;i<=n;++i)
lg2[i]=lg2[i/
2]+
1;
for(
int i=
1;i<=n;++i){
mn[i][
0]=mx[i][
0]=a[i];
f[i][i]=
1;
}
for(
int j=
1;(
1<<j)<=n;++j)
for(
int i=
1;i+(
1<<j)-
1<=n;++i){
mn[i][j]=min(mn[i][j-
1],mn[i+(
1<<(j-
1))][j-
1]);
mx[i][j]=max(mx[i][j-
1],mx[i+(
1<<(j-
1))][j-
1]);
}
for(
int i=
1;i<=n;++i){
int cur=i;
for(
int j=i+
1;j<=n;++j){
int minn=formin(i,j);
int maxx=formax(i,j);
if(maxx-minn!=j-i){
f[i][j]=
0;
continue;
}
if(formin(i,j)<formin(i,cur))
f[i][j]=
1;
else
f[i][j]=f[i][cur]+
1;
cur=j;
}
}
}
int solve(){
int ans=max(
1,f[
1][n]);
for(
int i=
1;i<=n;++i){
if(i==
1 || (f[
1][i-
1] && formin(
1,i-
1)==
1)){
for(
int j=i;j<=n;++j){
if(!f[i][j])
continue;
if(formin(i,j)==
1)
break;
int k=formax(i,j);
if(k==n || (f[k+
1][n] && formax(k+
1,n)==n)){
for(
int t=j+
1;t<=k;++t){
if(f[t][k] && formin(t,k)==i)
ans=max(ans,f[
1][i-
1]+
1+f[j+
1][t-
1]+
1+f[k+
1][n]);
}
}
}
}
}
return ans;
}
int main(){
int T;
cin>>T;
while(T--){
scanf(
"%d",&n);
for(
int i=
1;i<=n;++i)
scanf(
"%d",&a[i]);
init();
printf(
"%d\n",solve());
}
}
