SPOJ, IKEYB, I KEYBOARD

SPOJ-IKEYB.cpp

#include <iostream>
#include <cstdio>

typedef unsigned long long ull;
typedef unsigned u;
using namespace std;
const u INF=1<<31;

u f[105];
char letter[105];
char key[105];
u dp[105][105], prev[105][105];
int K,L,T;

int sol(){
  int ckt;
	for(int k=0;k<=K;k++)
		for(int l=0;l<=L;l++)
			dp[k][l] = INF;
	dp[0][0] = 0;
	for(int k=1;k<=K;k++){
		for(int l=1;l<=L;l++){
			ckt = 0;
			for(int cnt=1, l1=l; l1<=L ;cnt++,l1++){
				ckt += cnt*f[l1];
				if(dp[k][l1] > dp[k-1][l-1]+ckt){
					dp[k][l1] = dp[k-1][l-1]+ckt;
					prev[k][l1] = l-1;
				}else if (dp[k][l1] == dp[k-1][l-1]+ckt){
					if(prev[k][l1] > l-1)
						prev[k][l1] = l-1;
				}
			}
		}
	}
	int print(int level, int len);
	print(K,L);
}

int print(int level, int len){
	if(level==0) return 0;
	print(level-1, prev[level][len]);
	
	cout << key[level] << ": ";
	for(int i=prev[level][len]+1; i<=len;i++)
		cout << letter[i];
	cout << endl; 
}

int main(){
	cin >> T;
	int z=1;
	while(T--){
		cin >> K >> L;
		cin >> (&key[1]);
		cin >> (&letter[1]);
		for(int i=1;i<=L;i++){
			cin >> f[i];
//			cout << f[i] << endl;
			}
		cout << "Keypad #"<<z<<":"<<endl; z++;
		sol();
		cout << endl;
	}
	return 0;
}