| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 478901 | 2021-10-09T04:38:08 Z | arwaeystoamneg | Group Photo (JOI21_ho_t3) | Java 11 | 0 ms | 0 KB |
import java.util.*;
import java.io.*;
class segment_tree// "segment tree"
{
int n;
int[]a;
segment_tree(int n)
{
this.n = n;
a = new int[n];
}
void update(int i,int j)
{
a[i] = j;
}
int query(int i,int j)
{
int ans= 0;
for(int k = i;k<j + 1;k++)ans += a[k];
return ans;
}
}
public class lab
{
public static void main(String[]args)
{
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] a= new int[n];
for(int i = 0;i<n;i++) {a[i] = sc.nextInt();a[i]--;}
int[]dp = new int[n + 1];
for(int i= 0;i<n+1;i++)dp[i] = 1000000000;
dp[n] = 0;
for(int i= n;i>=0;i--)
{
int val = dp[i];
ArrayList<Integer>b = new ArrayList<Integer>();
for(int y:a)if(y<i)b.add(y);
int[]idx = new int[i];
for(int j = 0;j<i;j++)idx[b.get(j)] = j;
segment_tree sum = new segment_tree(i);
for(int j= i -1;j>=0;j--)
{
val += i - idx[j] - 1;
val -=sum.query(0,idx[j]);
sum.update(idx[j],1);
dp[j] = Math.min(dp[j],val);
}
}
System.out.println(dp[0]);
}
}