Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

By adzo261, history, 12 months ago, ,

Editorials are not available in English and I am not able to approach this problem on my own.

 » 12 months ago, # |   0 Here is my solution which is different from the official one. (My English is very poor, sorry)Let dp[i][j] be the maximum number of digits of the answer, which is made with i matches and has j as the first(highest) digit.Thus we can easily get dp[i + c[A[k]]][A[k]] = max(dp[i + c[A[k]]][A[k]], dp[i][A[j]] + 1), where A[i] means the i-th available digit and c[i] means the cost of digit i.Finally, we can greedily output the answer. For i, the number of matches left now, consider a best j with max{f[i][j]}. If there exists some js with the same value, just use the maximum j. This strategy is correct, because when we compare two numbers, we first consider their total length, and then from high digits to low digits.Here is my solution for a better understanding :)