两道编程题，一道模拟一道dp
题目一
题意
有一叠扑克牌，每张牌介于1和10之间
有四种出牌方法：
- 单出1张
- 出2张对子
- 出五张顺子，如12345
- 出三连对子，如112233
给10个数，表示1-10每种牌有几张，问最少要多少次能出完
思路
爆搜
dfs 1-10，每次枚举能否按照四种情况出牌，如果当前牌出完了，dfs下一个，否则继续dfs当前值
复杂度大概在
题目二
题意
首先定义上升字符串，,比如aaa，abc是，acb不是
给n个上升字符串，选择任意个拼起来，问能拼出来的最长上升字符串长度
思路
排序+dp
首先按照字符串最后一个字母，由小到大排序，如果最后一个相同，按第一个由小到大
然后定义dp数组，dp[i]表示以字母'a'+i结尾的最长上升字符串长度
枚举输入的字符串，假设当前是s，l=s[0]-'a',r=*s.rbegin()-'a'
那么
复杂度大概
全部评论
(52) 回帖