f*******4
发帖数: 64 | 1 手里14张牌,牌面A~N,可能有重复.出牌规则是:
* 2,3,4张同样牌面
* 3张顺子
* A可以作任何牌使用
实现函数，返回全出掉的最少次数:
int Discard(const string &s); // assert(s.size()==14), 无法出掉返回-1
如"A,B,C,D,D,D,D,E,F,G,H,I,J,N"一种出法是
[B,C,D] [D,D,D] [E,F,G] [H,I,J] [A,N] | f****e
发帖数: 34 | 2 动态规划？一共就2^14状态。
用记忆化搜索，程序应该不难写。
【在 f*******4 的大作中提到】
: 手里14张牌,牌面A~N,可能有重复.出牌规则是:
: * 2,3,4张同样牌面
: * 3张顺子
: * A可以作任何牌使用
: 实现函数，返回全出掉的最少次数:
: int Discard(const string &s); // assert(s.size()==14), 无法出掉返回-1
: 如"A,B,C,D,D,D,D,E,F,G,H,I,J,N"一种出法是
: [B,C,D] [D,D,D] [E,F,G] [H,I,J] [A,N]
| k***7
发帖数: 6 | 3 string先排序，统计'A'出现的个数记为K，构建一个二维数组opt[K][14-K]
最优子结构为
opt[i][j] = {
//same cards
s[j]==s[j-1]?opt[i][j-2]:-1,
s[j]==s[j-1]&&s[j]==s[j-2]?opt[i][j-3]:-1,
s[j]==s[j-1]&&s[j]==s[j-2]&&s[j]==s[j-3]?opt[i][j-4]:-1,
//sequence
s[j]==s[j-1]+1&&s[j]==s[j-2]+2?opt[i][j-3]:-1,
//use 'A' card as same card
opt[i-1][j-1],
opt[i-2][j-1],
opt[i-3][j-1],
opt[i-4][j-1],
//use 'A' card as sequence
s[j]==s[j-1]+1||s[j]==s[j-1]+1?opt[i-1][j-2]:-1, //1 'A'
opt[i-2][j-1]// 2'A'
} => filter(-1) => getMin
opt[i][j] = -1 if (i + j<2) | B*****g
发帖数: 34098 | 4 就会递归，哈哈
【在 f*******4 的大作中提到】
: 手里14张牌,牌面A~N,可能有重复.出牌规则是:
: * 2,3,4张同样牌面
: * 3张顺子
: * A可以作任何牌使用
: 实现函数，返回全出掉的最少次数:
: int Discard(const string &s); // assert(s.size()==14), 无法出掉返回-1
: 如"A,B,C,D,D,D,D,E,F,G,H,I,J,N"一种出法是
: [B,C,D] [D,D,D] [E,F,G] [H,I,J] [A,N]
| l*****t
发帖数: 2019 | 5 看得我满脑子pattern matching加递归。我得写上个一整天。
【在 f*******4 的大作中提到】
: 手里14张牌,牌面A~N,可能有重复.出牌规则是:
: * 2,3,4张同样牌面
: * 3张顺子
: * A可以作任何牌使用
: 实现函数，返回全出掉的最少次数:
: int Discard(const string &s); // assert(s.size()==14), 无法出掉返回-1
: 如"A,B,C,D,D,D,D,E,F,G,H,I,J,N"一种出法是
: [B,C,D] [D,D,D] [E,F,G] [H,I,J] [A,N]
| B*****g
发帖数: 34098 | 6 大牛不可能用一天吧？
【在 l*****t 的大作中提到】
: 看得我满脑子pattern matching加递归。我得写上个一整天。
| s*****r
发帖数: 108 | | f*******4
发帖数: 64 | 8 不明觉厉
【在 f****e 的大作中提到】
: 动态规划？一共就2^14状态。
: 用记忆化搜索，程序应该不难写。
| f*******4
发帖数: 64 | 9 想了想，觉得很厉害
【在 k***7 的大作中提到】
: string先排序，统计'A'出现的个数记为K，构建一个二维数组opt[K][14-K]
: 最优子结构为
: opt[i][j] = {
: //same cards
: s[j]==s[j-1]?opt[i][j-2]:-1,
: s[j]==s[j-1]&&s[j]==s[j-2]?opt[i][j-3]:-1,
: s[j]==s[j-1]&&s[j]==s[j-2]&&s[j]==s[j-3]?opt[i][j-4]:-1,
: //sequence
: s[j]==s[j-1]+1&&s[j]==s[j-2]+2?opt[i][j-3]:-1,
: //use 'A' card as same card
| m*****n
发帖数: 204 | 10 DP, 15 min using top-down approach (memorization)
【在 f*******4 的大作中提到】
: 手里14张牌,牌面A~N,可能有重复.出牌规则是:
: * 2,3,4张同样牌面
: * 3张顺子
: * A可以作任何牌使用
: 实现函数，返回全出掉的最少次数:
: int Discard(const string &s); // assert(s.size()==14), 无法出掉返回-1
: 如"A,B,C,D,D,D,D,E,F,G,H,I,J,N"一种出法是
: [B,C,D] [D,D,D] [E,F,G] [H,I,J] [A,N]
| x***y
发帖数: 633 | 11 Convert this to a graph problem by using a node for a set of cards, and a
directed edge between 2 nodes if the first set of cards can be transformed
to 2nd set by playing the card once.
Then, this is a Dijkstra problem. |
|
