度小满 第三题

update:
只有算法岗三道题。


没写完,只过了36%好像,思路应该没问题,初始化和边界都没考虑清楚就瞎写交了。
我大概的思路是动态规划。
m和n都是200以内的数字,做一个201*201的矩阵。
状态是能不能赢。
方法考虑切一刀之后,剩下的两块给了对手,如果能做到切出来的两块都必然LOSE,那这把就稳了。

f(i,j) = WIN    如果能找到一组 f(i-a,j) 和f(i,j-b)都是LOSE    这里ab只要不越界就行。
不然就LOSE。

举个例子,算f(4,2)的时候,我发现 f(2,2)是LOSE,那我就切两块2*2,把失败留给对手。
虽然复杂度有点高,但是数字本来就小,而且只用算一次矩阵,后面直接从表里读就行了。

#度小满#
全部评论

相关推荐

02-23 12:32
已编辑
门头沟学院 嵌入式工程师
King987:学历没有问题,然后既然有实习经历的话,把这个放在上面多写一点,哪怕你自己包装一下,只要能圆回来就行,既然有实习经历的话,肯定主要看实习经历之类的。然后也会主要问这里多准备准备
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务