Skip to content

Instantly share code, notes, and snippets.

@osjayaprakash
Created January 16, 2013 17:29
Show Gist options
  • Save osjayaprakash/4548994 to your computer and use it in GitHub Desktop.
Save osjayaprakash/4548994 to your computer and use it in GitHub Desktop.
SPOJ, IKEYB, I KEYBOARD
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment