c.c

// Compiled with -O3
// cat C-large-practice.in  0.00s user 0.00s system 81% cpu 0.003 total
// ./a.out  4.18s user 0.13s system 99% cpu 4.318 total

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define NOT_FOUND 0xFFFFFFFF
#define MAX_PRISONERS 10000

int solve(unsigned int * mem, unsigned int * prisoners, unsigned int start, unsigned int end) {
    unsigned int best = NOT_FOUND;
    int i, cost;

    if (start >= end) {
        return 0;
    }
    if (mem[start * MAX_PRISONERS + end] != NOT_FOUND) {
        return mem[start * MAX_PRISONERS + end];
    }

    for (i = start; i < end; i++) {
        if (prisoners[i]) {
            unsigned int cost = solve(mem, prisoners, start, i)
                     + solve(mem, prisoners, i + 1, end);
            if (cost < best) {
                best = cost;
            }
        }
    }

    if (best != NOT_FOUND) {
        cost = end - start - 1 + best;
    }
    mem[start * MAX_PRISONERS + end] = cost;
    return cost;
}

int main(int argc, char** argv) {
    int num_cases, i;

    // Array of prisoners, will be marked with prisoners to remove
    unsigned int * prisoners = (int *) malloc(sizeof(int) * MAX_PRISONERS);

    // Memoization
    unsigned int * mem = (int *) malloc(sizeof(int) * MAX_PRISONERS * MAX_PRISONERS);

    scanf("%d", &num_cases);
    for (i = 0; i < num_cases; i++) {
        int p, q, j, cost;
        scanf("%d %d", &p, &q);

        // Reset mem and prisoners
        memset(mem, NOT_FOUND, sizeof(int) * MAX_PRISONERS * p);
        memset(prisoners, 0, sizeof(int) * p);

        // Set prisoners to remove
        for (j = 0; j < q; j++) {
            int prisoner;
            scanf("%d", &prisoner);
            prisoners[prisoner - 1] = 1;
        }

        // Get best case cost
        cost = solve(mem, prisoners, 0, p);

        printf("Case #%d: %u\n", i + 1, cost);
    }

    return 0;
}

c.py

# cat C-large-practice.in  0.00s user 0.00s system 82% cpu 0.003 total
# python c.py  103.58s user 0.16s system 99% cpu 1:43.83 total

import sys

mem = None

def solve(prisoners, start, end):
    if start >= end:
        return 0
    if end in mem[start]:
        return mem[start][end]

    best = None
    for p in xrange(start, end):
        if prisoners[p]:
            cost = solve(prisoners, start, p) + solve(prisoners, p + 1, end)
            if best == None or cost < best:
                best = cost

    if best == None:
        cost = 0
    else:
        cost = end - start - 1 + best

    mem[start][end] = cost
    return cost

for case in xrange(int(sys.stdin.readline())):
    p, q = sys.stdin.readline().split(' ')
    p, q = int(p), int(q)
    prisoners = [False] * p
    for cell in [int(x) for x in sys.stdin.readline().split(' ')]:
        prisoners[cell - 1] = True

    mem = {}
    for i in xrange(p):
        mem[i] = {}

    coins = solve(prisoners, 0, len(prisoners))
    print 'Case #%d: %d' % (case + 1, coins)