Advertisement
erek1e

IOI '00 P1 - Palindrome

Jun 8th, 2022
457
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.65 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<vector<short>> dp(n);
  12.     // dp[i][j] = min characters to add to make s[i],...,s[i+j-1] a palindrome
  13.     for (int i = 0; i < n; ++i) dp[i].resize(n-i+1);
  14.     for (int sz = 2; sz <= n; ++sz) {
  15.         for (int left = 0; left+sz <= n; ++left) {
  16.             int right = left+sz-1;
  17.             if (s[left] == s[right]) dp[left][sz] = dp[left+1][sz-2];
  18.             else dp[left][sz] = min(dp[left+1][sz-1], dp[left][sz-1]) + 1;
  19.         }
  20.     }
  21.     cout << dp[0][n] << endl;
  22.     return 0;
  23. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement