LSORTVN - LSORT
Tác giả: khuc_tuan
Ngôn ngữ: C++
#include <iostream>
using namespace std;
int a[1010], vt[1010];
int n;
int F[1010][1010], L[1010][1010], R[1010][1010];
int calc_left(int l, int r) {
if (l == r)
return vt[l];
if (L[l][r] != -1)
return L[l][r];
return L[l][r] = calc_left(l, r - 1) - (vt[r] < vt[l] ? 1 : 0);
}
int calc_right(int l, int r) {
if (l == r)
return vt[l];
if (R[l][r] != -1)
return R[l][r];
return R[l][r] = calc_right(l + 1, r) - (vt[l] < vt[r] ? 1 : 0);
}
int calc(int l, int r) {
if (l > r)
return 0;
if (F[l][r] != -1)
return F[l][r];
return F[l][r] = min(calc(l + 1, r) + (r - l + 1) * calc_left(l, r), calc(l, r - 1) + (r - l + 1) * calc_right(l, r));
}
int main() {
scanf("%d", &n);
for(int i=0;i<n;++i) scanf("%d", a + i);
for(int i=0;i<n;++i) vt[a[i] - 1] = i + 1;
memset( F, -1, sizeof(F));
memset( R, -1, sizeof(R));
memset( L, -1, sizeof(L));
int res = calc( 0, n-1);
printf("%d\n", res);
return 0;
}