Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define all(x) (x).begin(),(x).end()
- using namespace std;
- const int MSIZE = 10101;
- bool Kek(char ch) {
- return (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z');
- }
- pair<bool, string> TypicalBadString(string& s, int type = 1) {
- if (s == "") return {0, ""};
- for (char ch : s) if (ch == '\n') return {0, ""};
- string name = "";
- for (char ch : s) {
- if (!Kek(ch)) {
- if (!type) return {0, ""};
- if (ch != ' ') {
- return {0, ""};
- } else {
- return {1, name};
- }
- } else {
- name += ch;
- }
- }
- return {1, name};
- }
- const int NSIZE = 505;
- int dp[NSIZE][NSIZE];
- int main() {
- #ifdef LOCAL
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- string s;
- char ch;
- while (ch = getchar()) {
- if (ch == EOF) break;
- s.push_back(ch);
- }
- vector<string> tag;
- int left = 0;
- int right = 0;
- bool bad = false;
- int ans = 0;
- int n = s.size();
- for (int i = 0; i < n; i++) {
- if (s[i] == '<') left = i;
- if (s[i] == '>') {
- tag.push_back(s.substr(left + 1, i - left - 1));
- }
- }
- vector<pair<string, int> > begins;
- vector<pair<string, int> > ends;
- int itr = 0;
- for (auto& s : tag) {
- if (s.size() == 0) {
- ans++;
- } else if (s[0] != '/') {
- auto [type, name] = TypicalBadString(s);
- if (name == "") ans++;
- else begins.push_back({name, itr});
- } else {
- s = s.substr(1, s.size() - 1);
- auto [type, name] = TypicalBadString(s, 0);
- if (name == "") ans++;
- else ends.push_back({name, itr});
- }
- itr++;
- }
- set<string> st;
- for (auto [str, ind] : begins) st.insert(str);
- for (auto [str, ind] : ends) st.insert(str);
- map<string, int> mp;
- itr = 1;
- for (string str : st) mp[str] = itr++;
- vector<pair<int,int> > full;
- for (auto [str, ind] : begins) full.push_back({ind, mp[str]});
- for (auto [str, ind] : ends) full.push_back({ind, -mp[str]});
- memset(dp, 0, sizeof dp);
- sort(all(full));
- vector<int> a;
- for (auto [ind, val] : full) a.push_back(val);
- n = a.size();
- for (int len = 1; len <= n; len++) {
- for (int l = 0; l + len <= n; l++) {
- int r = l + len - 1;
- if (l == r) {
- continue;
- } else {
- for (int i = l; i <= r; i++) {
- dp[l][r] = max(dp[l][r], dp[l][i] + dp[i + 1][r]);
- }
- if (a[l] == -a[r] && a[l] == abs(a[l])) {
- dp[l][r] = max(dp[l][r], dp[l + 1][r - 1] + 1);
- }
- }
- }
- }
- int used = dp[0][n - 1];
- cout << ans + a.size() - used * 2 << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement