JMK no matter what

SPOJ 문제 링크: 집에 우분투 컴퓨터 셋업하고 처음으로 푼 문제. Standard DP. 답 역추적이 관건인데, 첫 번째 개수를 최소화하는 것과 마지막 개수를 최대화하는 것이 꼭 동치는 아니기 때문에.. 애초에 답을 거꾸로 계산해야 한다. 한번에 맞음.;

lang:cpp
#include<iostream>
#include<cstring>
#include<algorithm>
#include<sstream>
#include<string>
#include<vector>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<fstream>
#include<cassert>
#include<numeric>
#include<set>
#include<map>
#include<queue>
#include<list>
#include<deque>
using namespace std;

#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define REP(i,n) FOR(i,0,n)
#define FORE(it,x) for(typeof(x.begin()) it=x.begin();it!=x.end();++it)
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define CLEAR(x,with) memset(x,with,sizeof(x))
#define sz size()
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef long long ll;

int n, m;
char keys[100], letters[100];
int freq[100];

int cache[100][100], bt[100][100];
// map first a letters into the first b keys
int minMap(int a, int b)
{
    if(a == 0) return 0;
    if(b == 0) return 987654321;
    int& ret = cache[a][b]; if(ret != -1) return ret;
    ret = 987654321;
    int costKeys = 0, sumKeys = 0;
    for(int i = 1; i <= a; ++i)
    {
        sumKeys += freq[a-i];
        costKeys += sumKeys; // the existing letters all require one more pushes
        int cand = costKeys + minMap(a-i, b-1);
        if(cand <= ret)
        {
            ret = cand;
            bt[a][b] = i;
        }
    }
    return ret;
}

// map first a letters into the first b keys
void backtrack(int a, int b)
{
    if(b == 0) return;
    minMap(a, b);    
    backtrack(a - bt[a][b], b-1);
    printf("%c: ", keys[b-1]);
    for(int i = bt[a][b]; i >= 1; --i)
        printf("%c", letters[a-i]);
    printf("\n");

}

int main()
{
    int cases;
    scanf("%d", &cases);
    for(int cc = 0; cc < cases; ++cc)
    {
        printf("Keypad #%d:\n", cc+1);
        CLEAR(cache,-1);
        scanf("%d %d", &n, &m);
        scanf("%s %s", keys, letters);
        REP(i,m) scanf("%d", &freq[i]);
        backtrack(m, n);
        printf("\n");
    }
}