Chỉ cần làm subtask đến độ phức tạp \(O(n^2)\) để thi hsg thành phố, nếu muốn full thì phải thành thạo ctdl (thi offline nên phải đảm bảo cài chuẩn)
Vì cách chia dạng dp như này gần như là học vẹt nên xem như là có công thức chung cho phần lớn các bài

Trạng thái chung:

• Gọi \(dp[i]\) là (độ dài/tổng) dãy con tăng (dài/lớn) nhất mà có điểm kết thúc tại là vị trí \(i\) (khi xét trong \(i\) phần tử đầu tiên, CÓ CHỌN vị trí thứ \(i\)).
• Có thể thêm trạng thái \(dp[i][0/1]\) với trường hợp dãy con tăng giảm xen kẽ để xét là đang tăng hay đang giảm.

Công thức tính:

• Thứ tự tính mảng dp là lần lượt từ trái qua phải (hoặc ngược lại đối với những bài cần truy vết theo thứ tự từ điển)
• Điều kiện cần phải quan tâm là điều kiện để nối được hai phần tử với nhau để tạo thành dãy con tăng (cụ thể là \(a_j < a_i\) và một vài điều kiện thêm nếu có)
• Tính chất chung của mọi dạng dp là dùng những bài toán nhỏ đã tính trước để có thể tính được bài toán lớn hơn. Cụ thể ở đây là dãy con tăng: khi đã biết có một các nào đó để chọn ra dãy con tăng có kết thúc tại vị trí \(j\) mà dài nhất có thể (độ dài là \(dp_j\)), thì nếu có thể thêm \(a_i\) vào sau \(a_j\) để tạo thành dãy vẫn thỏa mãn thì cập nhật \(dp_i\) mới chính bằng \(dp_j + 1\).
  
  C++

  // gán trạng thái ban đầu (nếu cần)
  dp[0] = 0; // dp[1] = 1; ...
  int ans = 1;
  for (int i = 1; i <= n; ++i) { // for từ trạng thái đầu tiên chưa được gán ban đầu
      dp[i] = 1; // tính trước giá trị nếu chỉ lấy một vị trí i
      for (int j = 1; j < i; ++j) { // duyệt các vị trí j trước đó
          // nếu a[i] có thể thêm vào sau a[j] để tạo thành dãy vẫn thỏa mãn thì cập nhật dp[i] mới
          if (a[j] < a[i])
              dp[i] = max(dp[i], dp[j] + 1);
      }
      ans = max(ans, dp[i]);
  }
  cout << ans;
  

Truy vết:

• Mỗi vị trí \(i\), ta cần biết được vị trí \(j\) nào đã được chọn để tạo nên kết quả trong \(dp[i]\), vị trí \(j\) đó ta sẽ lưu vào mảng \(trace_i\)
• Giải sử trong đoạn code trên, dp[i] chỉ được cập nhật max khi \(a_j < a_i\), và \(dp_j\) chỉ thực sự "có ý nghĩa" khi nó làm thai đổi \(dp_i\), tức là \(dp_j + 1 > dp_i\) thì lúc đó ta sẽ gán \(trace_i = j\)
  
  C++

  for (int i = 1; i <= n; ++i) {
      dp[i] = 1;
      for (int j = 1; j < i; ++j) {
          if (a[j] < a[i]) {
              if (dp[j] + 1 > dp[i]) {
                  dp[i] = dp[j] + 1;
                  trace[i] = j;
              }
          }
      }
  }
  

  
  Để làm gọn phần lấy max dp, có thể viết hàm maximize trả về 0/1 tương ứng với giá trị có được cập nhật hay không cùng với biến tham chiếu để cập nhật kết quả mới
  
  C++

  bool maxi(int &x, int y) {
      // biến tham chiếu x nếu bị thay đổi giá trị trong hàm này thì biến được nạp vào từ bên ngoài cùng thay đổi theo
      if (x < y) return x = y, 1;
      return 0;
  }
  ...
  for (int i = 1; i <= n; ++i) {
      dp[i] = 1;
      for (int j = 1; j < i; ++j)
          if (a[j] < a[i] && maxi(dp[i], dp[j] + 1))
              trace[i] = j;
  }
  

• Để in ra mảng sau khi tính \(dp\) và \(trace\), chỉ cần xác định đúng vị trí \(i\) mà \(dp_i\) cho ra kết quả tối ưu sau đó lần lượt nhảy về phía đầu, đảo ngược dãy in ra:
  
  C++

  int ans = 0, pos;
  for (int i = 1; i <= n; ++i)
      if (maxi(ans, dp[i]))
          pos = i;
  vector<int> tr;
  while (pos > 0) {
      tr.push_back(pos);
      pos = trace[pos];
  }
  for (int i = tr.size() - 1; i >= 0; --i) cout << tr[i] << ' ';
  

Với độ phức tạp \(O(n^2)\) là đủ cho HSG thành phố rồi, còn những bài trong contest có subtask với giới hạn lớn thì có thể phải thay đổi trạng thái dp để có thể áp dụng cấu trúc dữ liệu. Tuy nhiên vẫn có phương pháp chung cho các dạng dãy con tăng:

• Gọi \(dp[x]\) là (độ dài/tổng) dãy con tăng (dài/lớn) nhất mà có phần tử kết thúc mang giá trị là \(x\) tính tới thời điểm hiện tại (về sau có thể sẽ bị ghi đè, lưu ý lúc truy vết)
• Thay vì lưu vào mảng dp thì lưu vào một cấu trúc dữ liệu có thể cập nhật điểm và lấy giá trị đoạn (segmen tree/bit)
• Đối với trường hợp dãy con tăng giảm xen kẽ thì nên dùng 2 mảng cấu trúc dữ liệu riêng biệt quản lí tăng/giảm, ctdl tăng có thể update cho một điểm ở ctdl giảm và ngược lại.

Solution:

Dãy con tăng dài nhất (bản dễ)

(đã có sol)

Dãy con tăng có tổng lớn nhất

Subtask1: 50%
Gọi \(dp[i]\) là tổng lớn nhất của dãy con tăng kết thúc tại vị trí i. Điều kiện để \(a[i]\) có thể thêm vào sau \(a[j]\) trước đó là \(j < i\) và \(a[j] < a[j]\):
\(maximize(dp[i], dp[j] + a[i])\)

ans = 0;
for (int i = 1; i <= n; ++i) {
    dp[i] = a[i];
    for (int j = 1; j < i; ++j)
        if (a[j] < a[i])
            dp[i] = max(dp[i], dp[j] + a[i]);
    ans = max(ans, dp[i]);
}

Subtask2: 50%
Đổi cách lưu trạng thái dp:
Gọi \(dp[x]\) là tổng lớn nhất của dãy con tăng kết thúc số có giá trị x. Điều kiện để \(a[i]\) có thể thêm vào sau \(x\) trước đó là \(x < a[i]\):
\(maximize(dp[a[i]], dp[x] + a[i])\)

ans = 0;
for (int i = 1; i <= n; ++i) {
    int last = 0; // tìm tổng dãy con tăng lớn nhất kết thúc tại một số nhỏ hơn a[i] để thêm a[i] vào
    for (int x = 1; x < a[i]; ++x)
        last = max(last, dp[x]);
    dp[a[i]] = max(dp[a[i]], last + a[i]);
}

Từ code trâu như trên có thể thấy vòng for x có ý nghĩa là lấy max các dp[x] với x < a[i] thì ta hoàn toàn có thể dùng cấu trúc dữ liệu (it/bit) để giải quyết với độ phức tạp tổng là \(O(nlogn)\).

ans = 0;
for (int i = 1; i <= n; ++i) {
    int last = getmax(a[i] - 1);
    update(a[i], last + a[i]);
}

Tuy nhiên còn một vấn đề nữa là \(a[i]\) quá lớn không thể dùng ctdl để quản lí đoạn lên đến \(10^9\). Cần thêm một thao tác nén mảng a đồng thời lưu lại giá trị ban đầu.

#include <bits/stdc++.h>                                                                                                                                                                                      //Logm
using namespace std;
#define int long long

const int N = 1e5+5;
int n, a[N];

vector<int> val;
int comp[N];

int bit[N];
void update(int i, int val) { // dp[i] = val
    for (; i < N; i += i & -i)
        bit[i] = max(bit[i], val);
}
int getmax(int i) { // lấy max(dp[1..i])
    int res = 0;
    for (; i > 0; i -= i & -i)
        res = max(res, bit[i]);
    return res;
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if (fopen("_ab.inp", "r")) {
        freopen("_ab.inp", "r", stdin);
        freopen("_ab.out", "w", stdout);
    }

    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        val.push_back(a[i]);
    }
    // sắp xếp tất cả giá trị và loại bỏ đi những giá trị trùng lặp
    sort(val.begin(), val.end());
    val.erase(unique(val.begin(), val.end()), val.end());
    // {2, 10, 4, 5, 2, 4, 4} -> {2, 4, 5, 10}

    // lưu ý vì ctdl bit không thể update hay get ở vị trí 0
    // nên cần +2 giá trị nén để không bị tràn
    for (int i = 1; i <= n; ++i)
        comp[i] = lower_bound(val.begin(), val.end(), a[i]) - val.begin() + 2;
    // a = {2, 10, 4, 5, 2, 4, 4}
    // comp = {2, 5, 3, 4, 2, 3, 3}

    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        int last = getmax(comp[i] - 1); // tìm dp[x] lớn nhất với x < a[i]
        // vì ở đây lấy max có vị trí comp[i] - 1 nên comp[i] phải > 1
        update(comp[i], last + a[i]); // thêm a[i] vào dp[x] lớn nhất và cập nhật cho dp[a[i]]
        ans = max(ans, last + a[i]); // lấy max kết quả
    }
    cout << ans;
    return 0;
}

CSES - Towers

Kết quả cần tìm là số nhóm ít nhất cần có để có thể lấy ra hết các phần tử của mảng a chia vào các nhóm sao cho khi giữ nguyên thứ tự trong mảng ban đầu thì mỗi nhóm đều phải là một dãy con tăng. Hay nói cách khác là tìm số lượng dãy con tăng ít nhất không giao nhau phủ hết mảng ban đầu. (sau đây tạm gọi là số nhóm tăng ít nhất)

Tính chất quan trọng: số nhóm tăng ít nhất của mảng bằng độ dài dãy con không tăng dài nhất của mảng đó. Tương tự với số nhóm giảm ít nhất của mảng bằng độ dài dãy con không giảm dài nhất của mảng đó.

Chứng minh: gg