fork download
copy 
  1. /*
  2. ID: untamed
  3. PROG: IOIPALIN
  4. LANG: C++
  5. */
  6.  
  7. #include<iostream>
  8. #include<algorithm>
  9. #include<string>
  10. #include<cstring>
  11. #include<vector>
  12. #include<stack>
  13. #include<queue>
  14. #include<deque>
  15. #include<map>
  16. #include<set>
  17. #include<limits>
  18. #include<climits>
  19. #include<cmath>
  20. #include<functional>
  21. #include<ctime>
  22. #include<cstdlib>
  23. #include<fstream>
  24. #include<typeinfo>
  25.  
  26. using namespace std;
  27.  
  28. typedef long long int ll;
  29. typedef short int i16;
  30. typedef unsigned long long int u64;
  31. typedef unsigned int u32;
  32. typedef unsigned short int u16;
  33. typedef unsigned char u8;
  34.  
  35. const int N = 5200;
  36.  
  37. int dp[N][N];
  38.  
  39. char s[N];
  40.  
  41. int n;
  42.  
  43. int main()
  44. {
  45.     scanf("%d\n%s", &n, s+1);
  46.  
  47.     int i,from,to;
  48.  
  49.     for(i=1;i<=n;i++)
  50.     {
  51.         dp[0][1]=1;
  52.     }
  53.     for(i=1;i<n;i++)
  54.     {
  55.         if(s[i]==s[i+1])
  56.             dp[1][i]=0;
  57.         else
  58.             dp[1][i]=1;
  59.     }
  60.  
  61.     for(i=2;i<=n;i++)
  62.     {
  63.         for(from=1;(to=from+i)<=n;from++)
  64.         {
  65.             if(s[from]==s[to])
  66.                 dp[i][from]=dp[i-2][from+1];
  67.             else
  68.                 dp[i][from]=1+min(dp[i-1][from],dp[i-1][from+1]);
  69.         }
  70.     }
  71.  
  72.     printf("%d\n", dp[n-1][1]);
  73.  
  74.     return 0;
  75. }
  76.  
Runtime error #stdin #stdout 0s 108800KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/oalges
language:
C++14 (gcc 8.3)
created:
9 years 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!