Advertisement
erek1e

IOI '00 P1 - Palindrome (2)

Jun 8th, 2022
617
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.78 KB | None | 0 0
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. int main() {
  9.     int n; string s;
  10.     cin >> n >> s;
  11.     vector<int> dp[3];
  12.     // dp[i] = min characters to add to make s[i],...,s[i+sz-1] a palindrome
  13.     /* dp[0] holds values for sz, dp[1] holds values for sz-1,
  14.     dp[2] holds values for sz-2 */
  15.     dp[0].resize(n), dp[1].resize(n), dp[2].resize(n);
  16.     for (int sz = 2; sz <= n; ++sz) {
  17.         dp[2] = dp[1];
  18.         dp[1] = dp[0];
  19.         for (int left = 0; left+sz <= n; ++left) {
  20.             int right = left+sz-1;
  21.             if (s[left] == s[right]) dp[0][left] = dp[2][left+1];
  22.             else dp[0][left] = min(dp[1][left+1], dp[1][left]) + 1;
  23.         }
  24.     }
  25.     cout << dp[0][0] << endl;
  26.     return 0;
  27. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement