fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4.  
  5. int main() {
  6.     ios::sync_with_stdio(false);
  7.     cin.tie(nullptr);
  8.     int n, m;
  9.     if (!(cin >> n >> m)) return 0;
  10.     vector<int> a(n+1), b(m+1);
  11.     for (int i = 1; i <= n; ++i) cin >> a[i];
  12.     for (int j = 1; j <= m; ++j) cin >> b[j];
  13.  
  14.     // lcs[i][j]: độ dài LCS của a[1..i] và b[1..j] mà kết thúc tại b_j (theo ảnh)
  15.     // f[i][j]: số dãy khác nhau có độ dài lcs[i][j] kết thúc tại b_j
  16.     vector<vector<int>> lcs(n+1, vector<int>(m+1, 0));
  17.     vector<vector<ll>> f(n+1, vector<ll>(m+1, 0));
  18.  
  19.     // định nghĩa bổ trợ: "vị trí 0" (không có phần tử) với lcs = 0 và có 1 dãy rỗng
  20.     for (int i = 0; i <= n; ++i) f[i][0] = 1; // f[i][0] = 1 (dãy rỗng)
  21.     for (int j = 0; j <= m; ++j) lcs[0][j] = 0, f[0][j] = 1;
  22.  
  23.     // xử lý O(n^3)
  24.     for (int i = 1; i <= n; ++i) {
  25.         for (int j = 1; j <= m; ++j) {
  26.             if (a[i] == b[j]) {
  27.                 // tìm lcs[i][j] = 1 + max_{0 <= t < j} lcs[i-1][t]
  28.                 int bestLen = 0;
  29.                 for (int t = 0; t < j; ++t) {
  30.                     bestLen = max(bestLen, lcs[i-1][t]);
  31.                 }
  32.                 lcs[i][j] = bestLen + 1;
  33.  
  34.                 // tính f[i][j] = sum f[i-1][t] với các t thỏa:
  35.                 // (1) lcs[i-1][t] + 1 == lcs[i][j]
  36.                 // (2) không tồn tại h in (t+1..j-1) sao cho b[h] == b[t]
  37.                 ll ways = 0;
  38.                 for (int t = 0; t < j; ++t) {
  39.                     if (lcs[i-1][t] + 1 != lcs[i][j]) continue;
  40.                     bool ok = true;
  41.                     // kiểm tra có phần tử bằng b[t] giữa t+1..j-1 hay không
  42.                     if (t != 0) { // nếu t==0 thì b[0] là "không có", luôn ok
  43.                         for (int h = t+1; h <= j-1; ++h) {
  44.                             if (b[h] == b[t]) { ok = false; break; }
  45.                         }
  46.                     }
  47.                     if (ok) ways += f[i-1][t];
  48.                 }
  49.                 f[i][j] = ways;
  50.             } else {
  51.                 // không dùng a[i], giữ giá trị từ i-1
  52.                 lcs[i][j] = lcs[i-1][j];
  53.                 f[i][j] = f[i-1][j];
  54.             }
  55.         }
  56.     }
  57.  
  58.     // tìm độ dài LCS lớn nhất (toàn chuỗi a[1..n], b[1..m]) và tổng số dãy KHÁC NHAU.
  59.     int L = 0;
  60.     for (int j = 1; j <= m; ++j) L = max(L, lcs[n][j]);
  61.  
  62.     // tổng các f[n][j] với lcs[n][j] == L, nhưng tránh đếm trùng do cùng giá trị b_j
  63.     ll ans = 0;
  64.     for (int j = 1; j <= m; ++j) {
  65.         if (lcs[n][j] != L) continue;
  66.         // nếu tồn tại k > j với b[k] == b[j] và lcs[n][k] == L thì bỏ qua j
  67.         bool hasLaterSame = false;
  68.         for (int k = j+1; k <= m; ++k) {
  69.             if (b[k] == b[j] && lcs[n][k] == L) { hasLaterSame = true; break; }
  70.         }
  71.         if (!hasLaterSame) ans += f[n][j];
  72.     }
  73.  
  74.     // nếu L == 0 thì chỉ có dãy rỗng: tùy yêu cầu bạn có thể in 0 và 1 (độ dài 0, 1 cách)
  75.     cout << L << " " << ans << "\n";
  76.     return 0;
  77. }
  78.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin 
5 4
1 2 1 4 3
1 4 2 3
stdout 
3 2
https://ideone.com/EqSYnV
language:
C++14 (clang 8.0)
created:
22 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!