Bình luận

• 
  

  0

  

  ToiNhoDuongThanhThao  đã bình luận lúc 11, Tháng 6, 2026, 3:26

  include <iostream>

  include <vector>

  include <string>

  include <algorithm>

  include <fstream>

  using namespace std;

  // Sử dụng mảng tĩnh để tối ưu bộ nhớ cho kích thước 1000x1000x11x2 int dp[1001][1001][11][2];

  int main() { iosbase::syncwith_stdio(false); cin.tie(NULL);

  ifstream cin_f("SPLIT.INP");
  ofstream cout_f("SPLIT.OUT");
  
  int n, m, k;
  if (!(cin_f >> n >> m >> k)) return 0;
  string s, t;
  cin_f >> s >> t;
  
  // Khởi tạo DP với giá trị rất nhỏ (đại diện cho không thể thực hiện)
  for (int i = 0; i <= n; ++i)
      for (int j = 0; j <= m; ++j)
          for (int l = 0; l <= k; ++l)
              dp[i][j][l][0] = dp[i][j][l][1] = -1e9;
  
  dp[0][0][0][0] = 0;
  
  for (int i = 0; i <= n; ++i) {
      for (int j = 0; j <= m; ++j) {
          for (int l = 0; l <= k; ++l) {
              // Trạng thái 0: Không chọn ký tự hiện tại hoặc kết thúc một xâu con
              if (i > 0) dp[i][j][l][0] = max(dp[i][j][l][0], max(dp[i - 1][j][l][0], dp[i - 1][j][l][1]));
              if (j > 0) dp[i][j][l][0] = max(dp[i][j][l][0], max(dp[i][j - 1][l][0], dp[i][j - 1][l][1]));
  
              // Trạng thái 1: Chọn ký tự khớp nhau s[i-1] == t[j-1]
              if (i > 0 && j > 0 && s[i - 1] == t[j - 1] && l > 0) {
                  // Tiếp tục xâu con cũ hoặc bắt đầu xâu con mới
                  int extend = dp[i - 1][j - 1][l][1] + 1;
                  int start = max(dp[i - 1][j - 1][l - 1][0], 0) + 1;
                  dp[i][j][l][1] = max(extend, start);
              }
          }
      }
  }
  
  int res = max(dp[n][m][k][0], dp[n][m][k][1]);
  if (res <= 0) cout_f << -1 << endl;
  else cout_f << res << endl;
  
  return 0;
  

  }

• 
  

  -3

  

  super_god  đã bình luận lúc 8, Tháng 10, 2024, 3:04

  hello ae