题目描述
有这么一款单人卡牌游戏,牌面由颜色和数字组成,颜色为红、黄、蓝、绿中的一种,数字为0-9中的一个。游戏开始时玩家从手牌中选取一张卡牌打出,接下来如果玩家手中有和他上一次打出的手牌颜色或者数字相同的手牌,他可以继续将该手牌打出,直至手牌打光或者没有符合条件可以继续打出的手牌。
现给定一副手牌,请找到最优的出牌策略,使打出的手牌最多。
输入描述
输入为两行
- 第一行是每张手牌的数字,数字由空格分隔,
- 第二行为对应的每张手牌的颜色,用r y b g这4个字母分别代表4种颜色,字母也由空格分隔。
手牌数量不超过10。
输出描述
输出一个数字,即最多能打出的手牌的数量。
用例
输入 | 1 4 3 4 5 r y b b r |
输出 | 3 |
说明 | 如果打(1, r)-> (5, r),那么能打两张。 如果打(4,y) -> (4, b) -> (3, b),那么能打三张。 |
输入 | 1 2 3 4 r y b l |
输出 | 1 |
说明 | 没有能够连续出牌的组合,只能在开始时打出一张手牌,故输出1 |
题目解析
本题连续出牌的条件是:
如果玩家手中有和他上一次打出的手牌颜色或者数字相同的手牌,他可以继续将该手牌打出
因此,我们可以基于回溯算法,来求解不同的出牌方式,而下张牌是否可出的条件是:
- 和上一张牌的数字相同,或者和上一张牌的颜色相同
Python算法源码
# 输入获取
nums = input().split()
colors = input().split()
def dfs(cards, used, last, count, ans):
ans[0] = max(ans[0], count)
for i in range(len(cards)):
if used[i]:
continue
cur = cards[i]
if last and last.num != cur.num and last.color != cur.color:
continue
used[i] = True
dfs(cards, used, cur, count + 1, ans)
used[i] = False
class Card:
def __init__(self, num, color):
self.num = num
self.color = color
# 算法入口
def getResult():
n = len(nums)
cards = [Card(nums[i], colors[i]) for i in range(n)]
ans = [0]
used = [False] * n
dfs(cards, used, None, 0, ans)
return ans[0]
# 算法调用
print(getResult())
题目描述
有这么一款单人卡牌游戏,牌面由颜色和数字组成,颜色为红、黄、蓝、绿中的一种,数字为0-9中的一个。游戏开始时玩家从手牌中选取一张卡牌打出,接下来如果玩家手中有和他上一次打出的手牌颜色或者数字相同的手牌,他可以继续将该手牌打出,直至手牌打光或者没有符合条件可以继续打出的手牌。
现给定一副手牌,请找到最优的出牌策略,使打出的手牌最多。
输入描述
输入为两行
- 第一行是每张手牌的数字,数字由空格分隔,
- 第二行为对应的每张手牌的颜色,用r y b g这4个字母分别代表4种颜色,字母也由空格分隔。
手牌数量不超过10。
输出描述
输出一个数字,即最多能打出的手牌的数量。
用例
输入 | 1 4 3 4 5 r y b b r |
输出 | 3 |
说明 | 如果打(1, r)-> (5, r),那么能打两张。 如果打(4,y) -> (4, b) -> (3, b),那么能打三张。 |
输入 | 1 2 3 4 r y b l |
输出 | 1 |
说明 | 没有能够连续出牌的组合,只能在开始时打出一张手牌,故输出1 |
题目解析
本题连续出牌的条件是:
如果玩家手中有和他上一次打出的手牌颜色或者数字相同的手牌,他可以继续将该手牌打出
因此,我们可以基于回溯算法,来求解不同的出牌方式,而下张牌是否可出的条件是:
- 和上一张牌的数字相同,或者和上一张牌的颜色相同
Python算法源码
# 输入获取
nums = input().split()
colors = input().split()
def dfs(cards, used, last, count, ans):
ans[0] = max(ans[0], count)
for i in range(len(cards)):
if used[i]:
continue
cur = cards[i]
if last and last.num != cur.num and last.color != cur.color:
continue
used[i] = True
dfs(cards, used, cur, count + 1, ans)
used[i] = False
class Card:
def __init__(self, num, color):
self.num = num
self.color = color
# 算法入口
def getResult():
n = len(nums)
cards = [Card(nums[i], colors[i]) for i in range(n)]
ans = [0]
used = [False] * n
dfs(cards, used, None, 0, ans)
return ans[0]
# 算法调用
print(getResult())
题目描述
有这么一款单人卡牌游戏,牌面由颜色和数字组成,颜色为红、黄、蓝、绿中的一种,数字为0-9中的一个。游戏开始时玩家从手牌中选取一张卡牌打出,接下来如果玩家手中有和他上一次打出的手牌颜色或者数字相同的手牌,他可以继续将该手牌打出,直至手牌打光或者没有符合条件可以继续打出的手牌。
现给定一副手牌,请找到最优的出牌策略,使打出的手牌最多。
输入描述
输入为两行
- 第一行是每张手牌的数字,数字由空格分隔,
- 第二行为对应的每张手牌的颜色,用r y b g这4个字母分别代表4种颜色,字母也由空格分隔。
手牌数量不超过10。
输出描述
输出一个数字,即最多能打出的手牌的数量。
用例
输入 | 1 4 3 4 5 r y b b r |
输出 | 3 |
说明 | 如果打(1, r)-> (5, r),那么能打两张。 如果打(4,y) -> (4, b) -> (3, b),那么能打三张。 |
输入 | 1 2 3 4 r y b l |
输出 | 1 |
说明 | 没有能够连续出牌的组合,只能在开始时打出一张手牌,故输出1 |
题目解析
本题连续出牌的条件是:
如果玩家手中有和他上一次打出的手牌颜色或者数字相同的手牌,他可以继续将该手牌打出
因此,我们可以基于回溯算法,来求解不同的出牌方式,而下张牌是否可出的条件是:
- 和上一张牌的数字相同,或者和上一张牌的颜色相同
Python算法源码
# 输入获取
nums = input().split()
colors = input().split()
def dfs(cards, used, last, count, ans):
ans[0] = max(ans[0], count)
for i in range(len(cards)):
if used[i]:
continue
cur = cards[i]
if last and last.num != cur.num and last.color != cur.color:
continue
used[i] = True
dfs(cards, used, cur, count + 1, ans)
used[i] = False
class Card:
def __init__(self, num, color):
self.num = num
self.color = color
# 算法入口
def getResult():
n = len(nums)
cards = [Card(nums[i], colors[i]) for i in range(n)]
ans = [0]
used = [False] * n
dfs(cards, used, None, 0, ans)
return ans[0]
# 算法调用
print(getResult())
题目描述
有这么一款单人卡牌游戏,牌面由颜色和数字组成,颜色为红、黄、蓝、绿中的一种,数字为0-9中的一个。游戏开始时玩家从手牌中选取一张卡牌打出,接下来如果玩家手中有和他上一次打出的手牌颜色或者数字相同的手牌,他可以继续将该手牌打出,直至手牌打光或者没有符合条件可以继续打出的手牌。
现给定一副手牌,请找到最优的出牌策略,使打出的手牌最多。
输入描述
输入为两行
- 第一行是每张手牌的数字,数字由空格分隔,
- 第二行为对应的每张手牌的颜色,用r y b g这4个字母分别代表4种颜色,字母也由空格分隔。
手牌数量不超过10。
输出描述
输出一个数字,即最多能打出的手牌的数量。
用例
输入 | 1 4 3 4 5 r y b b r |
输出 | 3 |
说明 | 如果打(1, r)-> (5, r),那么能打两张。 如果打(4,y) -> (4, b) -> (3, b),那么能打三张。 |
输入 | 1 2 3 4 r y b l |
输出 | 1 |
说明 | 没有能够连续出牌的组合,只能在开始时打出一张手牌,故输出1 |
题目解析
本题连续出牌的条件是:
如果玩家手中有和他上一次打出的手牌颜色或者数字相同的手牌,他可以继续将该手牌打出
因此,我们可以基于回溯算法,来求解不同的出牌方式,而下张牌是否可出的条件是:
- 和上一张牌的数字相同,或者和上一张牌的颜色相同
Python算法源码
# 输入获取
nums = input().split()
colors = input().split()
def dfs(cards, used, last, count, ans):
ans[0] = max(ans[0], count)
for i in range(len(cards)):
if used[i]:
continue
cur = cards[i]
if last and last.num != cur.num and last.color != cur.color:
continue
used[i] = True
dfs(cards, used, cur, count + 1, ans)
used[i] = False
class Card:
def __init__(self, num, color):
self.num = num
self.color = color
# 算法入口
def getResult():
n = len(nums)
cards = [Card(nums[i], colors[i]) for i in range(n)]
ans = [0]
used = [False] * n
dfs(cards, used, None, 0, ans)
return ans[0]
# 算法调用
print(getResult())
题目描述
有这么一款单人卡牌游戏,牌面由颜色和数字组成,颜色为红、黄、蓝、绿中的一种,数字为0-9中的一个。游戏开始时玩家从手牌中选取一张卡牌打出,接下来如果玩家手中有和他上一次打出的手牌颜色或者数字相同的手牌,他可以继续将该手牌打出,直至手牌打光或者没有符合条件可以继续打出的手牌。
现给定一副手牌,请找到最优的出牌策略,使打出的手牌最多。
输入描述
输入为两行
- 第一行是每张手牌的数字,数字由空格分隔,
- 第二行为对应的每张手牌的颜色,用r y b g这4个字母分别代表4种颜色,字母也由空格分隔。
手牌数量不超过10。
输出描述
输出一个数字,即最多能打出的手牌的数量。
用例
输入 | 1 4 3 4 5 r y b b r |
输出 | 3 |
说明 | 如果打(1, r)-> (5, r),那么能打两张。 如果打(4,y) -> (4, b) -> (3, b),那么能打三张。 |
输入 | 1 2 3 4 r y b l |
输出 | 1 |
说明 | 没有能够连续出牌的组合,只能在开始时打出一张手牌,故输出1 |
题目解析
本题连续出牌的条件是:
如果玩家手中有和他上一次打出的手牌颜色或者数字相同的手牌,他可以继续将该手牌打出
因此,我们可以基于回溯算法,来求解不同的出牌方式,而下张牌是否可出的条件是:
- 和上一张牌的数字相同,或者和上一张牌的颜色相同
Python算法源码
# 输入获取
nums = input().split()
colors = input().split()
def dfs(cards, used, last, count, ans):
ans[0] = max(ans[0], count)
for i in range(len(cards)):
if used[i]:
continue
cur = cards[i]
if last and last.num != cur.num and last.color != cur.color:
continue
used[i] = True
dfs(cards, used, cur, count + 1, ans)
used[i] = False
class Card:
def __init__(self, num, color):
self.num = num
self.color = color
# 算法入口
def getResult():
n = len(nums)
cards = [Card(nums[i], colors[i]) for i in range(n)]
ans = [0]
used = [False] * n
dfs(cards, used, None, 0, ans)
return ans[0]
# 算法调用
print(getResult())
标签:200,used,打出,Python,OD,手牌,num,ans,cards
From: https://blog.csdn.net/qq_30247949/article/details/140349642