let menu = ["Home", "Algorithms", "CodeHub", "VNOI Statistics"];

Overview

VOI 2016 SEQ189

solution.md

Chú ý: Input mẫu ở SPOJ bị sai, input đúng là dãy số như trong đề:

6
7 3 5 1 9 21

Trước hết ta cần sắp xếp lại dãy số tăng dần, sau đó giải bằng QHĐ trạng thái.

Đặt \(F(i,k)\) là dãy SEQ189 dài nhất chọn từ \(A_1\) đến \(A_i\), với \(k\) là trạng thái được chọn/không được chọn của số:

  • Bit thứ j của k = 1 nếu trong dãy được chọn có số \(A_i-j\).

Vì ta chỉ quan tâm tới 10 giá trị gần nhất nên có \(2^{10}\) trạng thái cần xét.

Kết quả của bài toán là \(n - max(F)\).

Ta tính \(F(i)\) từ \(F(i-1)\) như sau:

  • Lần lượt xét các trạng thái \(k\), ta tạo trạng thái mới \(k'\) bằng cách dịch trái \(k\) đi \(a_{i}-a_{i-1}\) bit, sau đó AND với 1023 để lấy 10 bit cuối cùng.
  • Trường hợp không chọn \(A_{i}\), \(F(i,k') = F(i-1, k)\).
  • Trường hợp chọn \(A_{i}\), \(F(i, k'|1) = F(i-1, k) + 1\). Để chọn được \(A_i\) ta phải có các bit thứ 1, 8 và 9 của \(k'\) đều bằng 0.

Vì có nhiều trạng thái \(k\) có thể sinh ra cùng một trạng thái \(k'\) nên ta sẽ lấy max như trong code.

main.cpp
Open in Github • Download 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MASK189 = (1<<1) + (1<<8) + (1<<9);

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n; cin >> n;
    vector<int> a(n);
    for (int &a: a) cin >> a;

    sort(a.begin(), a.end());

    vector<int> f(1024), f1(1024);
    f.assign(1024, -1);
    f[0] = 0;
    f[1] = 1;

    for (int i=1; i<n; i++) {
        int d = a[i] - a[i-1];
        f1.assign(1024, -1);
        for (int k=0; k<1024; k++) {
            if (f[k] >= 0) {
                int k1 = d>=10? 0 : (k<<d)&1023;
                f1[k1] = max(f1[k1], f[k]);
                if ((k1 & MASK189) == 0) {
                    f1[k1|1] = max(f1[k1|1], f[k] + 1);
                }
            }
        }
        f.swap(f1);
    }

    int res = 0;
    for (int k=0; k<1024; k++) {
        res = max(res, f[k]);
    }
    cout << n - res;
    return 0;
}
Comments