讨论/算法和数据结构/关于最长子序,动态规划和分治算法的题求解/
关于最长子序,动态规划和分治算法的题求解

您的朋友正在开发棋盘游戏。他们提出了如下的设计,它是一行连续的整数序列,颜色为绿色或红色。
1.png
每个玩家都有一个令牌,可以用来在棋盘上移动。规则如下:
•玩家可以选择任何正方形作为起点。
•如果正方形为绿色,则它们必须向右移动(以任意数量的正方形)到一个数字大于当前数字的正方形。
•如果正方形为红色,则它们必须向左移动
以任意数量的正方形)到一个大于其当前数字的正方形。
•重复此操作,直到没有可用的移动,然后游戏完成。当所有玩家结束后,获胜最多的玩家将获胜。
您的任务是设计一个使用动态编程的算法,以在指定的电路板布局作为输入的情况下始终赢得这场比赛。也就是说,您的算法将接收n个整数A [0 ... n-1]的数组和n个颜色C [0 ... n-1]∈{r,g}的数组,分别对应于具有相同索引的单元格。您的算法应返回一个索引序列I [0 ... k-1],该序列代表游戏中可能出现的最长移动顺序(玩家按照完成顺序放置令牌的单元格的索引) 。它是满足以下条件的电路板布局的最长子序列:
•对于所有j,0≤I [j]≤n-1。 •对于所有j I [j]。 •如果C [I [j]]为红色,则I [j + 1] <I [j]。
如果存在多个最长相同长度的此类序列,则您的算法可能会返回任何一个。在最初的示例中,结果将是:
2.png
(小数字是数组A中的索引,这是算法实际返回的值。)
其他示例:
3.png
4.png

展开讨论
小板砖发起于 2020-05-24
共 0 个讨论
无讨论