3581: 扑克牌题解

leaf posted @ 2015年2月25日 23:46 in 未分类 , 499 阅读

这题很早就碰到了,感觉很神,做法很怪异,题解看不懂。今年丽洁WC又讲了,终于下定决心把它搞掉。。

今天在去领会了一下,其实想法也挺自然的。。

首先,分成两类边:

1.只有数字相同,color不同

2.color同,数字不做要求

可以想象,如果把2类边删去,一行将变成一块一块的,我们只关心每一块的头尾颜色,这样,可以转换为三种颜色三个点,之间有一些边,我们可以将一块压缩成一条边,这样暴力dp找一条路径经过所有的边

然后注意到每一块数字都是相同的,且数字相同,颜色相同的不超过三张,这意味着总共不超过9张,搜!开一个hash记录每种边数量的状态(9种边),然后再开个数组像背包一样每种数字转移过来。。

这样就算出每种状态的数量,再乘上该状态下欧拉路径的数量加起来即可。

复杂度 最终转换的图状态只有几百w左右,跑得出来很,没有理论上的那么多


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter