Submission #535088

#	Time	Username	Problem	Language	Result	Execution time	Memory
535088		Cookie197	Group Photo (JOI21_ho_t3)	C++17	100 / 100	1034 ms	201412 KiB

Main

#include<iostream>
#include<algorithm>
#include<vector>
#include<set>

using namespace std;
#define ll long long
#define pii pair<ll,ll> 
#define mp make_pair
#define endl "\n"
#define out(x) cout<< #x << " = " << x << endl
#define outp(x) cout << #x << " first = " << x.first << " second = " << x.second << endl
#define inf 3e18
int n;
int arr[5005], pos[5005];

int a[5005][5005]; // 預處理，[i,i+1, ... j] 這個區間放在正確位置，會出現幾個逆序
int arev[5005][5005];
int b[5005][5005]; // 預處理，前i個自排列[舊的]，第i+1到j個為-1的遞減[新的]，舊的和新的之間會產生幾個逆序

int dp[5005];

vector<int> bit(5005);
void init(){
    for (int i=1;i<=n;i++) bit[i] = 0;
}
void add(int id,int x){
    for (int i=id;i<=n;i+=(i&-i)) bit[i] += x;
}
int sum(int id){
    if (id==0) return 0;
    int ans = 0;
    for (int i=id;i>=1;i-=(i&-i)) ans += bit[i];
    return ans;
}

signed main(){
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n;
    for (int i=1;i<=n;i++) cin>>arr[i], pos[arr[i]] = i;
    
    // precalc a
    for (int i=1;i<=n;i++){
        init();
        for (int j=i;j<=n;j++){
            a[i][j] = a[i][j-1] + sum(n) - sum(pos[j]-1);
            arev[i][j] = (j-i)*(j-i+1)/2 - a[i][j];
            add(pos[j],1);
        }
    }

    // precalc b
    for (int i=1;i<=n;i++){
        init();
        for (int z=1;z<=i;z++) add(pos[z],1);
        for (int j=i+1;j<=n;j++){
            b[i][j] = b[i][j-1] + i - sum(pos[j]-1);
        }
    }

    // dp[i] = 目前看到前i個位置，逆序最小數量
    for (int i=1;i<=n;i++){
        dp[i] = 1e9;
        for (int j=0;j<i;j++){
            dp[i] = min(dp[i], dp[j] + arev[j+1][i] + b[j][i]);
            //cout<<i+1<<" "<<j<<"   "<<arev[j+1][i]<<endl;
            //cout<<i<<" "<<j<<"   "<<b[j+1][i]<<endl;
        }

    }

    cout<<dp[n]<<endl;
}

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 32 / 32
• Subtask 4: 20 / 20
• Subtask 5: 36 / 36