Advertisement
Fshl0

Untitled

Oct 5th, 2021
879
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.66 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define F first
  3. #define S second
  4.  
  5. using namespace std;
  6.  
  7. const int N = 17;
  8.  
  9. string s[N];
  10. int dp[N][1 << N], maxDP[N][1 << N];
  11. vector <pair <string, int> > substrings[N];
  12.  
  13. int main () {
  14.     int n;
  15.     cin >> n;
  16.    
  17.     for (int i = 1; i <= n; i++) {
  18.         cin >> s[i];
  19.        
  20.         for (int msk = 1; msk < (1 << s[i].length()); msk++) {
  21.             string tmp = "";
  22.             for (int j = 0; j < (int) s[i].length(); j++)
  23.                 if (msk & (1 << j))
  24.                     tmp += s[i][j];
  25.            
  26.             substrings[i].push_back ({tmp, msk});
  27.         }
  28.        
  29.         sort (substrings[i].begin(), substrings[i].end());
  30.     }
  31.    
  32.     memset (dp, -1, sizeof (dp));
  33.     memset (maxDP, -1, sizeof (maxDP));
  34.    
  35.     for (int i = 0; i < (int) substrings[1].size(); i++) {
  36.         int msk = substrings[1][i].S;
  37.        
  38.         dp[1][msk] = __builtin_popcount (msk);
  39.         maxDP[1][msk] = dp[1][msk];
  40.        
  41.         if (i > 0) {
  42.             int last = substrings[1][i - 1].S;
  43.             maxDP[1][msk] = max (maxDP[1][last], dp[1][msk]);
  44.         }
  45.     }
  46.    
  47.     for (int i = 2; i <= n; i++) {     
  48.         for (int j = 0; j < (int) substrings[i].size(); j++) {
  49.             int msk = substrings[i][j].S;
  50.             string str = substrings[i][j].F;
  51.            
  52.             auto it = lower_bound (substrings[i - 1].begin(), substrings[i - 1].end(), make_pair (str, msk));
  53.             if (it == substrings[i - 1].begin())
  54.                 continue;
  55.            
  56.             --it;
  57.             int pre = (*it).S;
  58.             dp[i][msk] = __builtin_popcount (msk) + maxDP[i - 1][pre];
  59.            
  60.             maxDP[i][msk] = dp[i][msk];
  61.             if (j > 0) {
  62.                 int lastMsk = substrings[i][j - 1].S;
  63.                 maxDP[i][msk] = max (dp[i][msk], maxDP[i][lastMsk]);
  64.             }
  65.         }
  66.     }
  67.    
  68.     int mx = -1;
  69.     for (int i = 0; i < (int) substrings[n].size(); i++)
  70.         mx = max (mx, dp[n][substrings[n][i].S]);
  71.        
  72.     cout << mx << "\n";
  73. }
  74.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement