hdu6403 Card Game(基环树+DP)

看着题觉得很有趣,想了很久没想出来,后来又看了题解发现,这题太好了,我得写一写。然后敲了快300行,然后上网查了别人的代码,100行就写完了,真的是感受到了差距。

网上的大神们直接用普通搜索,外加边点的数量关系,就算出来了弱联通分量,判断出了是不是树或者基环树,然后我用了tarjan和一堆定制搜索才判断出图的形态。光这一点就差距的非常大了。

然后我自己将树和基环树的情况分开讨论,又写了一大堆定制搜索,才讨论完,然后大神们直接一个搜索,最后处理了下基环上的边就ok了,dp的十分简单,感觉差距真的太大了。

相比之下,自己的代码丑到没法看。自己要加油努力了。这次得好好学习下大神们的代码技巧。

这题最神的还是构图,看到卡片上数字的大小又范围,我就觉得肯定会以数字做文章。构图是把反面的数字连到正面数字上,然后我们通过一些操作,改变边的方向,从而使没有一个数字的入度超过1。这个构图真的太神了。

然后我们发现,只有树和基环树可以实现。对于树我们可以上下两次dp,来求出每个点做根的操作次数。对于基环树,我们考虑环上的顺逆,树的方向是确定的。然后就可以求解了。

代码太丑,就不放了

发表评论