SPOJ IKEYB - I-Keyboard

Problem Link: https://www.spoj.pl/NSUDP/problems/IKEYB/

Description for this problem is really long. In short -

Given the set of keys on a keypad, a set of letters to assign on those keys sequentially and each letters' frequency on a dictionary, you have to design an optimal keypad layout (assign letters to keys) such that overall typing price is lowest. The price is determined as the sum of the prices of each letter. The price of a letter is a product of the letter frequency (Fi) and its position on the key.

Now we can construct a dynamic programming solution to calculate the best solution taking k keys and l letters. If we know the solution for (k,l) then we can build solutions for (k+1,l+1), (k+1, l+2) .... (k+1, L-1) by assigning 1, 2, ... L-1-l letters respectively on key k+1. Initialization of this approach is trivial - we'll assign 1, 2, ... L letters on the first key.

We'll also need to track which letter is assigned to which key. So for each (key, end letter) pair, we'll need to store the starting index of the letter for this particular key.

Time complexity of this solution is O(K*L^2) and memory complexity O(K*L). Do you know any better way to solve this problem?

Source code -

#include <stdio.h>

#define rep(i,n) for(i=0;i<(n);i++)
#define MAXL 95
#define MAXK 95
#define INF 1023456789


int K,L, F[MAXL];
char keys[MAXK], letters[MAXL];

int dp[MAXK][MAXL];
int pi[MAXK][MAXL];

void solve() {
 int i,j,k,cur;
 rep(i,K) rep(j,L) dp[i][j] = INF;
 rep(i, K) {
  if(i == 0) { //initialize for first key
   rep(j, L) {
    if(j == 0) { 
     dp[i][j] = F[j]; 
     pi[i][j] = 0; 
    }
    else { 
     dp[i][j] = dp[i][j-1] + F[j] * (j+1); 
     pi[i][j] = 0;
    }
   }
   continue;
  }

  rep(j,L) if(dp[i-1][j] < INF) {
   cur = 0;
   for(k=j+1;k<L;k++) {
    cur += F[k] * (k-j);
    if(dp[i-1][j] + cur < dp[i][k]) {
     dp[i][k] = dp[i-1][j] + cur;
     pi[i][k] = j+1;
    }
   }
  }
 }
}

void print(int k, int l) {
 if(k < 0) return;
 print(k-1, pi[k][l]-1);
 printf("%c: ",keys[k]);
 int i;
 for(i=pi[k][l];i<=l;i++) printf("%c",letters[i]);
 printf("\n");
}

int main() {
 int T,kase=1;
 int i;
 scanf(" %d",&T);
 while(T--) {
  printf("Keypad #%d:\n",kase++);
  scanf(" %d %d",&K,&L);
  scanf(" %s",keys);
  scanf(" %s",letters);
  rep(i,L) scanf(" %d",&F[i]);

  solve();
  print(K-1,L-1);
  printf("\n");
 }
 return 0;
}