SWERC 2010: Assembly Line [Solved]

This is the problem I was getting Time Limit Exceeded as mentioned in the post. Thanks to emotionalBlind and moshiur for sharing their approaches. Previously I was trying to do a top down DP of finding optimal result within a start and end index which produces a certain character output. Now, I've switched my approach to bottom up. I am still storing results for the state [start index, end index, character i want to make]. But I'm also saving the characters I can make in a range of start and end index into a vector. So, when we split at different positions, instead of trying all characters, we only have to try the characters that we can make on the sub-range.



Source code below -

/*
Problem Name : Assembly Line
Problem Number : Live Archive 4961
Link : http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4961
Problem Type : Dynamic Programming
Difficulty : 6 / 10
Interest : 6 / 10
Complexity : O((NK)^3)
Date : November 30, 2010
*/
#include<string>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cassert>
using namespace std;

#define INF 302345678
#define min(a,b) (((a) < (b)) ? (a) : (b))
#define rep(i,n) for(i=0;i<(n);i++)

vector<string> parse(const string& s,const string& delim=" ") {
 vector<string>res;
 string t;
 for(int i=0;i!=s.size();i++) {
  if(delim.find(s[i]) != string::npos) {
   if(!t.empty()) {
    res.push_back(t);
    t="";
   }
  }
  else t+=s[i];
 }
 if(!t.empty()) res.push_back(t);
 return res;
}

#define MAXK 26
#define MAXN 200

int n; //input character ordering sequence length
char ch[MAXK+3]; //input character ordering sequence
int pos[200]; //position of a lower case letter in the input sequence..like pos['e'] = 1 in the 2nd sample
char tran[MAXK+3][MAXK+3]; //character part of input matrix
int cost[MAXK+3][MAXK+3]; //number part of input matrix

int dp[MAXN+2][MAXN+2][MAXK+2]; //dp table
char s[MAXN+5]; //query string
int L; //query string length

//vector< char > result[MAXN+2][MAXN+2];
char result[MAXN+2][MAXN+2][MAXK+2];
int counter[MAXN+2][MAXN+2];


void process() {
 int i,j,k,x,y;
 char a,b,c;
 int cst;
 rep(i,L) rep(j,L) counter[i][j] = 0;
 rep(i,L) {
  dp[i][i][s[i]-'a'] = 0;
  result[i][i][counter[i][i]++] = s[i];
 }
 for(i=2;i<=L;i++) {
  rep(j,L-i+1) {
   for(k=j;k<j+i-1;k++) {
    rep(x,counter[j][k]) rep(y,counter[k+1][j+i-1]) {
     a = result[j][k][x];
     b = result[k+1][j+i-1][y];
     c = tran[pos[a]][pos[b]];
     cst = cost[pos[a]][pos[b]] + dp[j][k][a-'a'] + dp[k+1][j+i-1][b-'a'];
     if(dp[j][j+i-1][c-'a'] == -1 || cst < dp[j][j+i-1][c-'a']) {
      dp[j][j+i-1][c-'a'] = cst;
     }
    }
   }
   rep(k,n) if(dp[j][j+i-1][ch[k]-'a'] != -1) result[j][j+i-1][counter[j][j+i-1]++] = ch[k];
  }
 }
}

int main()
{
 vector<string> t;
 int i,j,k;
 string res;
 int q;
 int cur, ret;
 bool f = 0;
 char temp[100];
 while(scanf("%d",&n)==1) {
  if(n == 0) break;
  if(!f) f = 1;
  else printf("\n");
  //input processing
  rep(i,n) { scanf(" %c",&ch[i]); pos[ch[i]] = i; }
  rep(i,n) rep(j,n) {
   scanf(" %s",s);
   t = parse(s,"-");
   cost[i][j] = atoi(t[0].c_str());
   tran[i][j] = t[1][0];
  }

  //queries
  scanf(" %d",&q);
  rep(i,q) {
   scanf(" %s",s);
   L = strlen(s);
   memset(dp,-1,sizeof(dp));
   process();
   res = "";
   ret = INF;
   rep(j,n) {
    cur = dp[0][L-1][ch[j]-'a'];
    if(cur != -1 && cur < ret) {
     ret = cur;
     sprintf(temp,"%d",ret);
     res = temp;
     res += "-";
     res += ch[j];
    }
   }
   assert(ret < INF);
   printf("%s\n",res.c_str());
  }
 } 
 return 0;
}