How to optimize enumeration?

Question

Search Engine Optimization

On one of the TV channels, the next lottery is held every week. During the week, participants make their bets. Each bet consists of naming some M-digit number in the base K number system (that is, in fact, each participant names M digits, each of which lies in the range from 0 to K-1). Leading zeros are allowed in numbers.
At some point, betting on the current draw ends, and after that, the presenter on TV calls the winning number (this is also an M-digit number in the K-ary number system). After that, those TV viewers, whose first digit of their number coincided with the first digit of the number named by the presenter, receive a win in the amount of A1 rubles. Those who match the first two digits of the number receive A2 rubles (at the same time, if the player has the second digit, but the first did not match, he does not receive anything). Similarly, those who guessed the first three digits receive A3 rubles. Etc. Those who guessed the whole number fully receive AM rubles. Moreover, if the player guessed the first t digits, then he receives At rubles, but does not receive prizes for guessing t–1, t–2, etc. digits. If the player didn't guess the first number, he gets nothing.
Write a program that, given the known bets made by viewers, finds the number that the TV presenter must name in order for the organizing company to pay out the minimum amount as winnings. For your convenience, bets made by players are already sorted in non-descending order.
Specifications Input
The first line of the input file INPUT.TXT contains the numbers N (the number of viewers who made their bets, 1<=N<=100000), M (the length of the numbers 1<=M<=10) and K (the number base 2< =K<=10). The next line contains M integers A1, A2, …, AM, specifying the payoffs in case only the first, first two,..., all digits match (1<=A1<=A2<=…<=AM<=100000). Each of the next N lines or one line contains one M-digit K-ary number separated by a space. The numbers are in non-decreasing order.
Output
In the output file OUTPUT.TXT print the smallest amount that you have to pay as a prize.
I am developing an attempt to solve with BFS, I lose a lot in terms of speed. Any ideas for a better method?

Answer 1

This problem can be solved without enumeration, in one pass.
If, when looking at numbers, we know at each moment what is the minimum sum S _i by matches longer than i digits for numbers that match the current one in the i first digits, and what is the number K _i of these matches for this sum, we can find out these characteristics for i -1, namely: at each change of the i-1st digit, if the next digit differs from the previous one by more than 1, S _i-1 = K _i-1 = 0 (because you can guess a number with a missing prefix); otherwise, S _i-1 = min(S _i ) + (L _i - K _{min(S i )} ) * A _i , where L _i-- the current number of numbers that match up to the i-th character.

Answer 2

#include <fstream>

using namespace std;

typedef long long x;
x N,M,K,j,I,A[11];

char p[2<<17][10];

x z(x i, x l, x r)
{
x m=x(2)<<35,t;
if (i>=M || l>=r)
m=0;
else
{
x L=l,R;
for (x c=48;c<K;c++)
{
for (R=L;R<r && p[R][i]==c; R++)
;
if (t=z(i+1,L,R), t<m)
m=t;
L=R;
}
}
return m+A[i]*(r-l);
}

int main()
{
fstream i("input.txt"),o("output.txt");
i>>N>>M>>K;
K+=48;
for (;I<M;I++)
i>>A[I+1];
for (;I>1;I--)
A[I]-=A[I-1];
for (;j<N;j++)
i>>p[j];
o<<z(0,0,N);
}

My decision. I coped with the worst scenario quite quickly, using a reasonable enumeration of options.
PS for the record it was required to write the shortest solution, so the code is like this.
PSS in some compilers needs to be changed o("output.txt")to o("output.txt",2)
If someone is interested, I can tell you how it works in the comments.