fork download 
  1. /*
  2.     I hate competitive programming.
  3.                     - sfsdaf_Orz -
  4. */
  5. #include <iostream>
  6. #include <vector>
  7. #include <map>
  8. #include <set>
  9. #include <unordered_map>
  10. #include <unordered_set>
  11. #include <cmath>
  12. #include <cstring>
  13. #include <numeric>
  14. #include <queue>
  15. #include <iomanip>
  16. #include <climits>
  17. #include <algorithm>
  18. #include <deque>
  19.  
  20. using namespace std;
  21. using ll = long long;
  22. using db = double;
  23. using pll = pair<ll, ll> ;
  24. using pii = pair<int, int>;
  25. using tpll = tuple<ll, ll, ll> ;
  26. #define f(i, a, b) for(int i = (a); i <= (b); i++)
  27. #define rf(i, a, b) for(int i = (a); i >= (b); i--)
  28. #define af(i, a, b, x) for(int i = (a); i <= (b); i += x)
  29. #define fr(i, a, b, x) for(int i = (a); i >= (b); i -= x)
  30. #define test() int t; cin >> t; while(t--)
  31. #define all(a) (a).begin(), (a).end()
  32. #define rall(a) (a).rbegin(), (a).rend()
  33. #define sz(a) (int)(a).size()
  34. #define pb push_back
  35. #define rv reverse
  36. #define rs resize
  37. #define fi first
  38. #define se second
  39. #define endl '\n'
  40. #define yes "YES"
  41. #define no "NO"
  42. #define gcd __gcd
  43. const ll maxn = 2001;
  44. const ll mod = 1e9 + 7;
  45. const int base = 31;
  46. const int INF = 1e9;
  47. string s, s1;
  48. int dp[maxn][maxn];
  49. void solve(){
  50.     cin >> s;
  51.     s1 = s;
  52.     rv(all(s1));
  53.     f(i, 1, sz(s)){
  54.         f(j, 1, sz(s)){
  55.             if(s[i - 1] == s1[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
  56.             else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
  57.         }
  58.     }
  59.     cout << sz(s) - dp[sz(s)][sz(s)];
  60. }
  61. int main()
  62. {
  63.     ios_base::sync_with_stdio(false);
  64.     cin.tie(nullptr);
  65.     cout.tie(nullptr);
  66.     solve();
  67. }
  68.  
Success #stdin #stdout 0.01s 5300KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/ZEikBc
language:
C++14 (gcc 8.3)
created:
13 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!