제출 #634787

#제출 시각UTC-0아이디문제언어결과실행 시간메모리
6347872022-08-25 03:42:42mdn2002Group Photo (JOI21_ho_t3)C++14
100 / 100
901 ms393032 KiB
#include<bits/stdc++.h>
using namespace std;
long long n , a [5003] , bs [5003][5003] , wr [5003] , dp [5003][5003];
int f ( int x , int y )
{
if ( x == n + 1 ) return 0;
if ( dp [x][y] != -1 ) return dp [x][y];
int ans = 1e9 , pos = x , posx = wr [y] + bs [y][ x - 1 ] , howmany = ( bs [y][ y - 1 ] - bs [y][ x - 1 ] );
if ( x != y ) ans = min ( ans , f ( y , y ) );
if ( y != n + 1 ) ans = min ( ans , f ( x , y + 1 ) + posx - pos - howmany );
return dp [x][y] = ans;
}
int main ()
{
memset ( dp , -1 , sizeof dp );
cin >> n;
for ( int i = 1 ; i <= n ; i ++ )
{
cin >> a [i];
wr [ a [i] ] = i;
}
for ( int i = 1 ; i <= n ; i ++ )
{
for ( int j = i ; j <= n ; j ++ ) bs [ a [i] ][ a [j] ] ++;
for ( int j = 1 ; j <= n ; j ++ ) bs [ a [i] ][j] += bs [ a [i] ][ j - 1 ];
}
cout << f ( 1 , 1 );
}
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...