Advertisement
Guest User

Untitled

a guest
Jul 21st, 2017
53
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.47 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <string>
  5. #include <cassert>
  6.  
  7. using namespace std;
  8.  
  9. const int inf = 1e9;
  10.  
  11. int main(){
  12. vector<pair<string, int> > v(1, make_pair(string(), 0));
  13. char c;
  14. int i = 0;
  15. while (cin.get(c)) {
  16. if (c == '<') {
  17. cin.get(c);
  18. if (c == '/')
  19. v[i].second = -1;
  20. else {
  21. v[i].second = 1;
  22. v[i].first += c;
  23. }
  24. while (cin.get(c)) {
  25. if ((c == '>') || (c == ' '))
  26. break;
  27. v[i].first += c;
  28. }
  29. }
  30. if (c == '>') {
  31. i++;
  32. v.push_back(make_pair(string(), 0));
  33. v.resize(i + 1);
  34. }
  35. }
  36. int n = v.size() - 1;
  37. if (n == 0) {
  38. cout << 0;
  39. return 0;
  40. }
  41.  
  42. vector <vector <int> > dp(n, vector <int>(n, inf));
  43.  
  44.  
  45.  
  46.  
  47. for (int i = 0; i <= n - 1; i++) {
  48. if (i == n - 1) {
  49. dp[n - 1][n - 1] = 1;
  50. break;
  51. }
  52. dp[i][i] = 1;
  53. if ((v[i].first == v[i + 1].first) && (v[i].second == 1) && (v[i + 1].second == -1))
  54. dp[i][i + 1] = 0;
  55. else
  56. dp[i][i + 1] = 2;
  57. }
  58.  
  59. for (int len = 3; len <= n; len++)
  60. for (int l = 0; l <= n - len; l++) {
  61. int r = l + len - 1;
  62. if ((v[l].first == v[r].first) && (v[l].second == 1) && (v[r].second == -1)) {
  63. for (int x = l; x < r; x++)
  64. dp[l][r] = min(dp[l][r], dp[l][x] + dp[x + 1][r]);
  65.  
  66. dp[l][r] = min(dp[l][r], dp[l + 1][r - 1]);
  67. }
  68. else
  69. for (int x = l; x < r; x++)
  70. dp[l][r] = min(dp[l][r], dp[l][x] + dp[x + 1][r]);
  71.  
  72.  
  73. }
  74.  
  75. cout << dp[0][n - 1];
  76. return 0;
  77. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement