Editorial for DMOPC '18 Contest 3 P2 - Bob and French Class
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
For 10% of marks, we can try every possible arrangement of French words and English words, making sure that no three consecutive words are in French. It takes time to check one arrangement, and there are
such arrangements, for an
algorithm.
For full marks, we will employ a dynamic programming approach. Let be the maximum mark attainable given that the first
words have had their language determined, and the longest suffix of French words currently determined has length
.
is therefore the maximum of
,
and
, incremented by the mark of word
in English.
, and
. The answer is therefore the maximum of
,
, and
.
Comments