Advertisement
Guest User

lcs.cpp

a guest
Jun 18th, 2019
112
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.98 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int maxn = 300 + 5;
  5. char a[maxn], b[maxn];
  6. int c[maxn], dp[maxn][maxn][maxn];
  7.  
  8. int main() {
  9.     scanf("%s", a + 1);
  10.     scanf("%s", b + 1);
  11.     int n = strlen(a + 1);
  12.     int m = strlen(b + 1);
  13.  
  14.     for (int i = 0; i < 3; ++i) scanf("%d", &c[i]);
  15.     int p; scanf("%d", &p);
  16.  
  17.     for (int i = 1; i <= n; ++i) {
  18.         if (a[i] == 'D') a[i] = 0;
  19.         if (a[i] == 'S') a[i] = 1;
  20.         if (a[i] == 'A') a[i] = 2;
  21.     }
  22.     for (int i = 1; i <= m; ++i) {
  23.         if (b[i] == 'D') b[i] = 0;
  24.         if (b[i] == 'S') b[i] = 1;
  25.         if (b[i] == 'A') b[i] = 2;
  26.     }
  27.  
  28.     for (int i = 0; i < maxn; ++i) {
  29.         for (int j = 0; j < maxn; ++j) {
  30.             for (int k = 0; k < maxn; ++k)
  31.                 dp[i][j][k] = -1e9;
  32.         }
  33.     }
  34.  
  35.     dp[0][0][p] = 0;
  36.     for (int i = 0; i <= n; ++i) {
  37.         for (int j = 0; j <= m; ++j) {
  38.             for (int k = 0; k <= p; ++k) {
  39.                 if (i + 1 <= n && j + 1 <= m) {
  40.                     if (a[i + 1] == b[j + 1])
  41.                         dp[i + 1][j + 1][k] = max(dp[i + 1][j + 1][k], dp[i][j][k] + 1);
  42.                 }
  43.                
  44.                 if (i + 1 <= n) {
  45.                     dp[i + 1][j][k] = max(dp[i + 1][j][k], dp[i][j][k]);
  46.                     if (k >= c[a[i + 1]])
  47.                         dp[i + 1][j][k - c[a[i + 1]]] = max(dp[i + 1][j][k - c[a[i + 1]]], dp[i][j][k] + 1);
  48.                 }
  49.  
  50.                 if (j + 1 <= m) {
  51.                     dp[i][j + 1][k] = max(dp[i][j + 1][k], dp[i][j][k]);
  52.                     if (k >= c[b[j + 1]])
  53.                         dp[i][j + 1][k - c[b[j + 1]]] = max(dp[i][j + 1][k - c[b[j + 1]]], dp[i][j][k] + 1);
  54.                 }
  55.             }
  56.         }
  57.     }
  58.  
  59.     int d = 1e9;
  60.     for (int i = 0; i < 3; ++i) d = min(d, c[i]);
  61.  
  62.     int ans = 0;
  63.     for (int i = 0; i <= p; ++i) {
  64.         ans = max(ans, dp[n][m][i] + i / (2 * d));        
  65.     }
  66.  
  67.     printf("%d\n", ans);
  68.     return 0;
  69. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement