Advertisement
999ms

Untitled

Sep 24th, 2019
177
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.98 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define all(x) (x).begin(),(x).end()
  3. using namespace std;
  4. const int MSIZE = 10101;
  5.  
  6. bool Kek(char ch) {
  7.     return (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z');
  8. }
  9.  
  10. pair<bool, string> TypicalBadString(string& s, int type = 1) {
  11.     if (s == "") return {0, ""};
  12.     for (char ch : s) if (ch == '\n') return {0, ""};
  13.     string name = "";
  14.     for (char ch : s) {
  15.         if (!Kek(ch)) {
  16.             if (!type) return {0, ""};
  17.             if (ch != ' ') {
  18.                 return {0, ""};
  19.             } else {
  20.                 return {1, name};
  21.             }
  22.         } else {
  23.             name += ch;
  24.         }
  25.     }
  26.     return {1, name};
  27. }
  28.  
  29. const int NSIZE = 505;
  30.  
  31. int dp[NSIZE][NSIZE];
  32.  
  33. int main() {
  34. #ifdef LOCAL
  35.     freopen("input.txt", "r", stdin);
  36.     freopen("output.txt", "w", stdout);
  37. #endif
  38.     ios_base::sync_with_stdio(false);
  39.     cin.tie(nullptr);
  40.     string s;
  41.     char ch;
  42.     while (ch = getchar()) {
  43.         if (ch == EOF) break;
  44.         s.push_back(ch);
  45.     }
  46.     vector<string> tag;
  47.     int left = 0;
  48.     int right = 0;
  49.     bool bad = false;
  50.     int ans = 0;
  51.     int n = s.size();
  52.     for (int i = 0; i < n; i++) {
  53.         if (s[i] == '<') left = i;
  54.         if (s[i] == '>') {
  55.             tag.push_back(s.substr(left + 1, i - left - 1));
  56.         }
  57.     }
  58.     vector<pair<string, int> > begins;
  59.     vector<pair<string, int> > ends;
  60.     int itr = 0;
  61.     for (auto& s : tag) {
  62.         if (s.size() == 0) {
  63.             ans++;
  64.         } else if (s[0] != '/') {
  65.             auto [type, name] = TypicalBadString(s);
  66.             if (name == "") ans++;
  67.             else begins.push_back({name, itr});
  68.         } else {
  69.             s = s.substr(1, s.size() - 1);
  70.             auto [type, name] = TypicalBadString(s, 0);
  71.             if (name == "") ans++;
  72.             else ends.push_back({name, itr});
  73.         }
  74.         itr++;
  75.     }
  76.     set<string> st;
  77.     for (auto [str, ind] : begins) st.insert(str);
  78.     for (auto [str, ind] : ends) st.insert(str);
  79.     map<string, int> mp;
  80.     itr = 1;
  81.     for (string str : st) mp[str] = itr++;
  82.     vector<pair<int,int> > full;
  83.     for (auto [str, ind] : begins) full.push_back({ind, mp[str]});
  84.     for (auto [str, ind] : ends) full.push_back({ind, -mp[str]});
  85.     memset(dp, 0, sizeof dp);
  86.     sort(all(full));
  87.     vector<int> a;
  88.     for (auto [ind, val] : full) a.push_back(val);
  89.     n = a.size();
  90.     for (int len = 1; len <= n; len++) {
  91.         for (int l = 0; l + len <= n; l++) {
  92.             int r = l + len - 1;
  93.             if (l == r) {
  94.                 continue;
  95.             } else {
  96.                 for (int i = l; i <= r; i++) {
  97.                     dp[l][r] = max(dp[l][r], dp[l][i] + dp[i + 1][r]);
  98.                 }
  99.                 if (a[l] == -a[r] && a[l] == abs(a[l])) {
  100.                     dp[l][r] = max(dp[l][r], dp[l + 1][r - 1] + 1);
  101.                 }
  102.             }
  103.         }
  104.     }
  105.     int used = dp[0][n - 1];
  106.     cout << ans + a.size() - used * 2 << endl;
  107. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement