v 0. Pasted by slipstak2 as cpp at 2011-10-25 19:48:01 MSK and set expiration to never.

Paste will expire never.

  1. // Очно-заочный кружок
  2. // Занятие №8. Олимпиадные задачи
  3. // Задача C. Почти палиндром
  4. // ibelyaev: 25Oct2011
  5. // http://cppalgo.blogspot.com/2011/04/blog-post.html
  6.  
  7. #include <iostream>
  8. #include <cstdio>
  9. #include <algorithm>
  10. #include <string>
  11. #include <string.h>
  12. #include <cmath>
  13. #include <queue>
  14. #include <vector>
  15. #include <map>
  16. #include <stdlib.h> // for exit(0)
  17. #include <stack>
  18. #include <list>
  19. #include <ctime>
  20. #include <set>
  21.  
  22. using namespace std;
  23.  
  24. const int MAX_SIZE = 5001;
  25. const int MAX_VALUE = 1e4;
  26. int n,k;
  27. short dp[MAX_SIZE][MAX_SIZE];
  28. string str;
  29. void input(){
  30.     scanf("%d %d", &n, &k);
  31.     cin>>str;
  32. }
  33. void solve(){
  34.     for (int len = 1; len < n; ++len) {
  35.         for (int i=0;i<n-len;++i) {
  36.             int j = i + len;
  37.             dp[i][j] = MAX_VALUE;
  38.             if (str[i] == str[j])
  39.                 dp[i][j] = dp[i+1][j-1];
  40.             else if (dp[i+1][j-1] + 1 <= k)
  41.                 dp[i][j] = dp[i+1][j-1] + 1;
  42.         }
  43.     }
  44. }
  45. void output() {
  46.     int res = n;
  47.     for (int i=0; i<n; ++i) {
  48.         for (int j = i+1; j<n; ++j)
  49.             if (dp[i][j] != MAX_VALUE)
  50.                 res++;
  51.     }
  52.     printf("%d", res);
  53. }
  54. int main()
  55. {
  56.     freopen("input.txt","r",stdin);
  57.     freopen("output.txt","w",stdout);
  58.  
  59.     input();
  60.     solve();
  61.     output();
  62.  
  63.     return 0;
  64. }


Editing is locked.