Участник:ZhenyaStrelkova/AIBOHP

Материал из DISCOPAL
Перейти к: навигация, поиск

https://www.spoj.com/problems/AIBOHP/

#include <iostream>
#include <algorithm>
#include <vector>
 
using namespace std;
 
const int maximum = 6107;
 
int main() {
 
    int T = 0, len = 0;
    int result[maximum][maximum];
    cin >> T;
    for (int t = 0; t < T; t++) {
        string sourceString;
        string newString;
        cin >> sourceString;
        len = sourceString.length();
        for (int i = 0; i < len; i++)
            newString += sourceString[len - 1 - i];
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                if (sourceString[i] == newString[j]) {
                    result[i][j] = (i > 0 && j > 0) ? result[i - 1][j - 1] + 1 : 1;
                } else {
                    int a = (i > 0) ? result[i - 1][j] : 0;
                    int b = (j > 0) ? result[i][j - 1] : 0;
                    result[i][j] = max(a, b);
                }
            }
        }
        cout << (len - result[len - 1][len - 1]) <<"\n";
    }
    return 0;
}