제출 #1213964

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1213964		minhpk	Group Photo (JOI21_ho_t3)	C++20	44 / 100	8 ms	1352 KiB

Main

#include <bits/stdc++.h>
using namespace std;

/*
  Giải thích tóm tắt các bước trong code:

  - Ta có hoán vị ban đầu A[1..N], LƯU vị trí pos[v] = index của giá trị v trong A.
    (Giả định A là hoán vị của {1..N}.)

  - DP[k] sẽ là chi phí (số nghịch thế) tối thiểu để xây một hoán vị B sao cho
    prefix B[1..k] (vốn gồm đúng tập {1..k} nhưng xếp thành một số khối đảo ngược liên tiếp)
    đã “ổn định” và thỏa a_i < a_{i+1} + 2 trong prefix.

  - Khi chuyển DP[j] → DP[k] (với j < k), ta thêm block mới {j+1, j+2, …, k}. Khối này
    sẽ nằm ngay sau prefix j và được đặt theo thứ tự [k, k-1, …, j+1]. Việc “đặt” block này
    phát sinh thêm một số nghịch thế (inversion) so với hoán vị ban đầu A:
      1. Mọi giá trị > k trong phần đã xét (prefix cũ) sẽ “va” với mỗi h ∈ {j+1..k}.
      2. Mọi giá trị g trong prefix cũ sao cho j < g < h, mỗi khi ta đặt h xuống sẽ “va” 1 lần.

    Ở đây, chúng ta sẽ tiền tính hai mảng:
      1) small_cnt[x][h] = số lượng các i < pos[h] sao cho A[i] nằm trong (x, h),
         tức x < A[i] < h.  (đóng góp kiểu “giữa j và h”)
      2) big_cnt[k][h]   = số lượng các i < pos[h] sao cho A[i] > k.        (đóng góp kiểu “> k”)

    - Với mỗi cặp (j,k), ta cần compute SUM_{h = j+1..k} [ big_cnt[k][h] + small_cnt[j][h] ].
      Gọi sum_big[k][t] = ∑_{h=1..t} big_cnt[k][h],
           sum_small[j][t] = ∑_{h=1..t} small_cnt[j][h].
      Khi đó, chi phí thêm của block {j+1..k} là
        cost_add(j→k) = ( sum_big[k][k]   - sum_big[k][j] )
                      + ( sum_small[j][k] - sum_small[j][j] ).

    - Cuối cùng, DP[k] = min_{0 ≤ j < k} { DP[j] + cost_add(j→k) }.
      Với DP[0] = 0 (tưởng tượng prefix rỗng, chưa xếp giá trị nào).

  Độ phức tạp:
   - Tính small_cnt[x][h] với ba vòng: x=0..N-1, h=x+1..N, rồi duyệt i=1..pos[h]-1  ⇒ O(N^3)
   - Tính big_cnt[k][h] với ba vòng: k=1..N, h=1..k, rồi duyệt i=1..pos[h]-1        ⇒ O(N^3)
   - Tạo prefix-sum sum_small và sum_big: O(N^2)
   - DP: hai vòng k=1..N, j=0..k-1 ⇒ mỗi bước O(1) tra công thức, tổng O(N^2)
   ⇒ Tổng ≈ O(N^3), với N ≤ 200 là hoàn toàn khả thi.
*/

static const int MAXN = 200;

int N;
int A[MAXN+1];      // A[1..N]: hoán vị ban đầu (mỗi số từ 1..N đúng một lần)
int pos[MAXN+1];    // pos[v] = index i sao cho A[i] = v

// small_cnt[x][h] = số i < pos[h] sao cho x < A[i] < h
// defined for 0 <= x < h <= N
int small_cnt[MAXN+1][MAXN+1];

// big_cnt[k][h] = số i < pos[h] sao cho A[i] > k
// defined cho 1 <= k <= N, 1 <= h <= k  (chỉ cần h <= k vì nếu h>k, block {j+1..k} không có h đó)
int big_cnt[MAXN+1][MAXN+1];

// sum_small[x][t] = ∑_{h=1..t} small_cnt[x][h]
// sum_big[k][t]   = ∑_{h=1..t} big_cnt[k][h]
long long sum_small[MAXN+1][MAXN+1];
long long sum_big[MAXN+1][MAXN+1];

long long DP[MAXN+1];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // --- Đọc input ---
    // Dạng: N (≤ 200), rồi A[1] A[2] ... A[N] (một hoán vị của 1..N)
    cin >> N;
    for(int i = 1; i <= N; i++){
        cin >> A[i];
    }
    // Tính pos[v]
    for(int i = 1; i <= N; i++){
        pos[ A[i] ] = i;
    }

    // --- Tiền tính small_cnt[x][h] ---
    // Với mọi 0 <= x < h <= N,
    //   small_cnt[x][h] = số i < pos[h] sao cho x < A[i] < h.
    // Lưu ý: h chạy từ 1..N; x có thể = 0..h-1.
    for(int x = 0; x <= N; x++){
        for(int h = x+1; h <= N; h++){
            int cnt = 0;
            int ph = pos[h];
            // đếm các i < ph
            for(int i = 1; i < ph; i++){
                if( A[i] > x && A[i] < h ){
                    cnt++;
                }
            }
            small_cnt[x][h] = cnt;
        }
    }

    // --- Tiền tính big_cnt[k][h] ---
    // Với mọi 1 <= k <= N, 1 <= h <= k,
    //   big_cnt[k][h] = số i < pos[h] sao cho A[i] > k.
    for(int k = 1; k <= N; k++){
        for(int h = 1; h <= k; h++){
            int cnt = 0;
            int ph = pos[h];
            for(int i = 1; i < ph; i++){
                if( A[i] > k ){
                    cnt++;
                }
            }
            big_cnt[k][h] = cnt;
        }
    }

    // --- Xây prefix-sum sum_small và sum_big ---
    // sum_small[x][t] = ∑_{h=1..t} small_cnt[x][h]
    // sum_big[k][t]   = ∑_{h=1..t} big_cnt[k][h]
    for(int x = 0; x <= N; x++){
        long long acc = 0;
        for(int t = 1; t <= N; t++){
            if(t <= x){
                // small_cnt[x][t] định nghĩa chỉ khi t > x
                // nếu t <= x, ta coi là 0
                // (vì h phải > x để small_cnt[x][h] có nghĩa)
                sum_small[x][t] = acc;
            } else {
                acc += small_cnt[x][t];
                sum_small[x][t] = acc;
            }
        }
    }
    for(int k = 1; k <= N; k++){
        long long acc = 0;
        for(int t = 1; t <= N; t++){
            if(t <= k){
                acc += big_cnt[k][t];
            }
            sum_big[k][t] = acc;
        }
    }

    // --- DP chính ---
    // DP[0] = 0 (prefix rỗng, chưa xếp gì).
    // DP[k] = min_{0 <= j < k} { DP[j] + cost_add(j→k) },
    // với cost_add(j→k) = (sum_big[k][k] - sum_big[k][j])
    //                    + (sum_small[j][k] - sum_small[j][j]).
    //
    // Giải thích: 
    //  - sum_big[k][k] - sum_big[k][j] = ∑_{h = j+1..k} big_cnt[k][h].
    //  - sum_small[j][k] - sum_small[j][j] = ∑_{h = j+1..k} small_cnt[j][h].
    //
    // DP tính tuần tự k = 1..N.

    const long long INF = (long long)1e18;
    for(int k = 0; k <= N; k++){
        DP[k] = INF;
    }
    DP[0] = 0;

    for(int k = 1; k <= N; k++){
        // Tính DP[k]
        for(int j = 0; j < k; j++){
            // cost_add(j→k):
            long long part_big   = sum_big[k][k]   - sum_big[k][j];
            long long part_small = sum_small[j][k] - sum_small[j][j];
            long long cost_add = part_big + part_small;

            long long cand = DP[j] + cost_add;
            if(cand < DP[k]){
                DP[k] = cand;
            }
        }
    }

    // Kết quả cuối cùng: DP[N]
    cout << DP[N] << "\n";
    return 0;
}

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