Paste will expire never.
- // Очно-заочный кружок
- // Занятие №8. Олимпиадные задачи
- // Задача C. Почти палиндром
- // ibelyaev: 25Oct2011
- // http://cppalgo.blogspot.com/2011/04/blog-post.html
- #include <iostream>
- #include <cstdio>
- #include <algorithm>
- #include <string>
- #include <string.h>
- #include <cmath>
- #include <queue>
- #include <vector>
- #include <map>
- #include <stdlib.h> // for exit(0)
- #include <stack>
- #include <list>
- #include <ctime>
- #include <set>
- using namespace std;
- const int MAX_SIZE = 5001;
- const int MAX_VALUE = 1e4;
- int n,k;
- short dp[MAX_SIZE][MAX_SIZE];
- string str;
- void input(){
- scanf("%d %d", &n, &k);
- cin>>str;
- }
- void solve(){
- for (int len = 1; len < n; ++len) {
- for (int i=0;i<n-len;++i) {
- int j = i + len;
- dp[i][j] = MAX_VALUE;
- if (str[i] == str[j])
- dp[i][j] = dp[i+1][j-1];
- else if (dp[i+1][j-1] + 1 <= k)
- dp[i][j] = dp[i+1][j-1] + 1;
- }
- }
- }
- void output() {
- int res = n;
- for (int i=0; i<n; ++i) {
- for (int j = i+1; j<n; ++j)
- if (dp[i][j] != MAX_VALUE)
- res++;
- }
- printf("%d", res);
- }
- int main()
- {
- freopen("input.txt","r",stdin);
- freopen("output.txt","w",stdout);
- input();
- solve();
- output();
- return 0;
- }
Editing is locked.