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

Overview

QBSEQ - Dãy con dài nhất có tổng chia hết cho K

solution.md

Đặt \(F(i, j)\) là dãy con dài nhất có tổng bằng \(j\), các phần tử của dãy con chọn từ \(A(1)\) đến \(A(i)\). Ta có công thức tính sau:

  • Khởi tạo: \(F(0,0) = 0\), các phần tử khác bằng \(-\infty\)
  • Lặp \(i\) từ 1 đến N, \(j\) từ 0 đến \(k-1\), tính: \(F(i, j) = max(F(i-1, j), F(i-1, (j-A(i))\bmod k) + 1)\)

Kết quả bài toán là \(F(n, 0)\).

Ta thấy \(F(i)\) được tính từ \(F(i-1)\) nên không cần phải dùng mảng 2 chiều khi cài đặt, chỉ cần 2 mảng \(F, G\) là đủ.

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

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

    int n, m; cin >> n >> m;
    vector<int> a(n);
    for (int &x: a) {
        cin >> x;
        x %= m;
    }

    vector<int> f(m, INT_MIN), g(m);
    f[0] = 0;
    for (int x: a) {
        for (int i=0; i<m; i++) {
            g[i] = max(f[i], f[(i-x+m) % m] + 1);
        }
        f.swap(g);
    }

    cout << f[0];
    return 0;
}
Comments