可以用动态解决问题,题目求的是最少的休息天数,我们可以通过求最大的工作天数来的得到答案。
用数组dp[ i ][ j ]记录到第 i 天为止最大的工作天数,j 的定义如下,
对于第 i 天 ,
• j=0,表示Vasya第 i 天休息,dp[ i ][0]就表示如果第 i 天休息的话,能得到的最大的工作天数(其它类似)。
• j=1 , 表示Vasya第 i 天 participated in the contest。
• j=2 , 表示Vasya第 i 天 went to gym。
那么,可以得到下面的状态转移方程。
CodeForces 698A Vacations
原文:http://www.cnblogs.com/cumulonimbus/p/5740575.html