spoj ⟼ classical ⟼ aibohp ⟼ aibohphobia

aibohp.cc

#include <bits/stdc++.h>
using namespace std;
int32_t testcases;
static char arr[6116];
static int mem[3][6116];

int main() {
    cin >> testcases;
    for (int test = 1; test <= testcases; ++test) {
        cin >> arr;
        int n = strlen(arr);
        int* dpy0 = mem[0];
        int* dpy1 = mem[1];
        int* dpy2 = mem[2];
        memset(mem[0], 0, sizeof(int)*6116);
        memset(mem[1], 0, sizeof(int)*6116);
        memset(mem[2], 0, sizeof(int)*6116);
        for (int y = 2; y <= n; ++y) {
            for (int x = 0; x < (n - y + 1); ++x) {
                dpy0[x] = min(dpy1[x + 1] + 1, dpy1[x] + 1);
                if (arr[x] == arr[x + y - 1] && dpy0[x] > dpy2[x + 1])
                    dpy0[x] = dpy2[x + 1];
            }
            swap(dpy0, dpy2); swap(dpy2, dpy1);
        }
        cout << dpy1[0] << endl;
    }
    return 0;
}

aibohp.py

#!/usr/bin/python
# -*- encoding: utf-8 -*-
# pylint: disable=invalid-name,missing-docstring,bad-builtin

def main():
    inf = float('inf')
    for _ in xrange(int(raw_input())):
        s = raw_input()
        n = len(s)
        dp = [[0]*x for x in xrange(n + 1, 0, -1)]
        for y in xrange(2, n + 1):
            for x in xrange(n - y + 1):
                dp[y][x] = min(
                    dp[y - 1][x + 1] + 1,
                    dp[y - 1][x] + 1,
                    dp[y - 2][x + 1] if s[x] == s[x + y - 1] else inf)
        print dp[-1][-1]

main()