#include <bits/stdc++.h>
using namespace std;
struct BIT{
vector<int> v;
int n;
BIT(int n1){
n=n1;
v.resize(n+1);
}
void add(int p,int x){
for(int i=p;i<=n;i+=i&(-i)){
v[i]+=x;
}
}
int ask(int p){
int ans=0;
for(int i=p;i>0;i-=i&(-i)){
ans+=v[i];
}
return ans;
}
};
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n;cin>>n;
vector<int> pos(n+1);
vector<vector<int>> cnt(n+2,vector<int>(n+2));
for(int i=1;i<=n;i++){
int k;cin>>k;
pos[k]=i;
}
for(int j=1;j<=n;j++){
BIT bit(n);
for(int i=j+1;i<=n;i++){
bit.add(pos[i],1);
}
for(int i=j;i>=1;i--){
cnt[i][j]=cnt[i+1][j]+bit.ask(pos[i]-1);
}
}
for(int i=1;i<=n;i++){
BIT bit(n);
int tmp=0;
for(int j=i;j<=n;j++){
tmp+=bit.ask(pos[j]);
cnt[i][j]+=tmp;
bit.add(pos[j],1);
}
}
vector<int> dp(n+1,INF);
dp[0]=0;
for(int i=1;i<=n;i++){
for(int j=0;j<i;j++){
dp[i]=min(dp[i],dp[j]+cnt[j+1][i]);
}
}
cout<<dp[n]<<endl;
return 0;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:51:24: error: 'INF' was not declared in this scope
51 | vector<int> dp(n+1,INF);
| ^~~
