VMSWAP - Đổi chỗ
Tác giả: skyvn97
Ngôn ngữ: C++
#include<cstdio>
#define MAX 3030
int a[MAX];
int h[MAX][MAX];
int l[MAX][MAX];
int n;
int fst,best;
int min(const int &x,const int &y) {
if (x<y) return (x); else return (y);
}
void init(void) {
scanf("%d",&n);
int i;
for (i=1;i<=n;i=i+1) scanf("%d",&a[i]);
}
void count(void) {
int i,j;
fst=0;
for (i=1;i<n;i=i+1)
for (j=i+1;j<=n;j=j+1)
fst=fst+(a[i]>a[j]);
for (i=1;i<=n;i=i+1) {
h[i][0]=0;
l[i][0]=0;
for (j=1;j<=n;j=j+1) {
h[i][j]=h[i][j-1]+(a[j]>a[i]);
l[i][j]=l[i][j-1]+(a[j]<a[i]);
}
}
}
void process(void) {
best=fst;
int i,j;
for (i=1;i<n;i=i+1)
for (j=i+1;j<=n;j=j+1) {
best=min(best,fst+(h[i][j-1]-h[i][i])+(l[j][j-1]-l[j][i])-(l[i][j-1]-l[i][i])-(h[j][j-1]-h[j][i])-(a[i]>a[j])+(a[i]<a[j]));
// printf("%d %d %d\n",i,j,best);
}
printf("%d",best);
}
int main(void) {
init();
count();
process();
return 0;
}