好久没有做题了..刷刷DP吧,之前都没有好好做过这方面的题,比赛一遇到就放过..没有一点思路.
这是个比较基础的,还好是我自己想出来的,没有看hints.对于每对猜测次数G和生命值L,需要得到一个最大的N,让其可以找到一个策略,能在G和L都没用完前猜出正确的数,即必胜策略. 我们平时玩这种游戏的时候都是二分..然后从经验上判断这个是最快能猜到那个数的.这里因为有生命值,所以复杂了些.我们假设这个某对GL对应的最大的N为nmax,第一步我们的必胜策略肯定是从中间找一个数k,然后判断这个数是大了还是小了还是刚好. 如果没有猜中,就从左边或者右边的范围内继续查找.假设dp[i][j]表示当猜测次数是i,生命值是j的时候能得到的最大的N.
再来看k,如果k猜大了,那么生命值就减少了1.需要从小于k的范围内再猜,在小于k的范围内所能得到的最大N是dp[i-1][j-1],在大于k的范围内的到最大N是dp[i-1][j],所以可得dp[i][j] = dp[i-1][j-1] + dp[i-1][j] + 1,这就是状态转移方程.
“钢琴的音符有12种,A,A# (A-sharp), B, C, C#, D, D#, E, F, F#, G, and G#,同时按下三个音符,有三种情况,一种是Major chord,一种是Minor chord，最后一种是什么都不是unrecognized，假设按下的这三个音符按顺序排列分别是a，b，c，如果ab中间隔3个，bc之间隔2个，那么整个结果就是a Major chord，如果ab中间隔2个，bc之间隔3个，那么整个结果是a Minor chord（假定12种音符在琴键上是循环排列），给定三个音符，然你判断结果是上述三种中的哪一种”
由于他给的音符的顺序不确定，大小写也不确定，一个音符的两个名称给哪个也不确定，而且输出是要求原样，类型要输出大写，-___-……所以我们一步一步来。。。保留输入的形式方便输出；把音符的两个名称转化为带#的形式，然后转换成大写；比较恶心的是他的顺序也不确定，但是给定的三个它们的最终结果是一样的，那么给12种音符赋值为20,21,22,23,2……210,211, 三种的值相加是唯一的，所以。。。。。
代码很丑，体现了我做模拟题的一贯风格：
（更多…）
“机器人模拟，给定一个A*B的地图，给定N个机器人的初始位置和方向，然后会有M个操作，判断这M是否能正常执行，如果能，输出“OK”，否则输出是出界还是与另外的机器人相撞。操作是一步一步执行的，没有两个同时发生，’R’,’L’,’F’分别表示向右转，向左转，向前进一步……”
步骤比较繁，但是没有什么陷阱，考耐心。此题麻烦的就是方向的转化，用一个dir数组保存方向的变化量，然后每个方向对应一个变化量。