fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int MAXN = 505;
  4.  
  5. int a[MAXN], b[MAXN];
  6. int lcs[MAXN][MAXN];
  7. long long f[MAXN][MAXN];
  8.  
  9. int main() {
  10.     ios::sync_with_stdio(false);
  11.     cin.tie(nullptr);
  12.     int n, m;
  13.     cin >> n >> m;
  14.     for(int i = 1; i <= n; i++) cin >> a[i];
  15.     for(int j = 1; j <= m; j++) cin >> b[j];
  16.  
  17.     // Khởi tạo: i=0 hoặc j=0 -> f = 1 (dãy rỗng)
  18.     for(int j = 0; j <= m; j++) f[0][j] = 1;
  19.  
  20.     for(int i = 1; i <= n; i++) {
  21.         for(int j = 1; j <= m; j++) {
  22.             if(a[i] == b[j]) {
  23.                 lcs[i][j] = 1;
  24.                 f[i][j] = 0;
  25.                 for(int t = 0; t < j; t++) {
  26.                     if(lcs[i-1][t] + 1 > lcs[i][j])
  27.                         lcs[i][j] = lcs[i-1][t] + 1, f[i][j] = 0;
  28.                 }
  29.                 for(int t = 0; t < j; t++) {
  30.                     // Check điều kiện không đếm trùng
  31.                     bool ok = true;
  32.                     for(int h = t+1; h < j; h++)
  33.                         if(b[h] == b[t]) { ok = false; break; }
  34.                     if(ok && lcs[i-1][t] + 1 == lcs[i][j])
  35.                         f[i][j] += f[i-1][t];
  36.                 }
  37.             } else {
  38.                 lcs[i][j] = lcs[i-1][j];
  39.                 f[i][j] = f[i-1][j];
  40.             }
  41.         }
  42.     }
  43.  
  44.     // Tìm độ dài LCS lớn nhất và số cách
  45.     int best = 0; long long ways = 0;
  46.     for(int j = 1; j <= m; j++)
  47.         best = max(best, lcs[n][j]);
  48.     for(int j = 1; j <= m; j++)
  49.         if(lcs[n][j] == best) ways += f[n][j];
  50.  
  51.     cout << best << " " << ways << "\n";
  52. }
  53.  
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
abadc
adbc
stdout
copy 
0 32767
https://ideone.com/sWLvQX
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!