算法吧 关注：30,702贴子：59,515
- 4回复贴，共1页
贪心算法应该可过，你的规则相对简单，不会出现如果想取得先手压牌就必须拆自己牌的复杂情况
如果有错误欢迎指出
设想一个链表，一个人A出牌a，另一个B必须出更大的牌b才能接续这个链表，直到一方不能接续链表，重开一个新的。
定理1，先出最小的牌的策略≥最优解。
如果一个链表是，最小-B-A-B结尾。而最优解是非最小-B-A-B-结尾。那么最优解里面一定有最小-B-A-B结尾。两个链表能交换的部分交换后一定能取得等价解。比如说，1358k是我的解的一部分，最优解包含2358k。因为最优解一定要把1打出去。某个包含1的链表的1和该链表的2交换一定是更有解。因为如果是12？？？这样的表的话，你12交换后，你先出2对面不能出，反而能卡对面一张卡。更优
定理2，先出最小的能压对方的牌＞＝最优解。
也是同理。对面1你直接k压了。然后你中间的牌不出了吗？也得出。交换链表对应部分来满足定理2给出的链表后，只会更优。
因为定理12的存在，显然可见，能压对面却不出牌只会更差
然后就是排序一下手牌。模拟一遍咯。只有最后两张牌时需要注意一下特例。因为最后的牌时，先压一波，开个新的链表，能在当前多打一张牌。久了其实又会被压一张回来。但是最后两张不给机会了
如果有错误欢迎指出
设想一个链表，一个人A出牌a，另一个B必须出更大的牌b才能接续这个链表，直到一方不能接续链表，重开一个新的。
定理1，先出最小的牌的策略≥最优解。
如果一个链表是，最小-B-A-B结尾。而最优解是非最小-B-A-B-结尾。那么最优解里面一定有最小-B-A-B结尾。两个链表能交换的部分交换后一定能取得等价解。比如说，1358k是我的解的一部分，最优解包含2358k。因为最优解一定要把1打出去。某个包含1的链表的1和该链表的2交换一定是更有解。因为如果是12？？？这样的表的话，你12交换后，你先出2对面不能出，反而能卡对面一张卡。更优
定理2，先出最小的能压对方的牌＞＝最优解。
也是同理。对面1你直接k压了。然后你中间的牌不出了吗？也得出。交换链表对应部分来满足定理2给出的链表后，只会更优。
因为定理12的存在，显然可见，能压对面却不出牌只会更差
然后就是排序一下手牌。模拟一遍咯。只有最后两张牌时需要注意一下特例。因为最后的牌时，先压一波，开个新的链表，能在当前多打一张牌。久了其实又会被压一张回来。但是最后两张不给机会了
