dango

  C++博客 :: 首页 :: 联系 :: 聚合  :: 管理
  11 Posts :: 0 Stories :: 4 Comments :: 0 Trackbacks

常用链接

留言簿(2)

我参与的团队

搜索

  •  

最新评论

阅读排行榜

评论排行榜

Hdu3229 Jinyuetuan Puzzle

题目大意:

    原题链接:http://acm.hdu.edu.cn/showproblem.php?pid=3229

    劲乐团游戏,得分种类:

1、  single note,按一下键得一个cool

2、  strip note,开始时按一下键得一个cool,结束时放开再得一个cool。若开始时miss或者中途放开按键,都不可以得到结束的cool。

键盘有一些冲突按键,如“1110000”代表前三个按键不可以同时按下,包括冲突按键的所有按键组合都会miss那一秒的所有note,例如“1110000”是冲突按键,“1110001”也会产生冲突。

 

题目分析:

    首先很容易想到这是一个动态规划问题,阶段是时间,状态是不同的按键状态。即可以用f[t][state]来表示第t秒结束后,按键状态为state时可以得到的分数。

    但是一些适当的优化是必要的,否则N*state*state*7,也就是1000*128*128*7加上多组测试数据,只要数据不是太水肯定会超过时限。

    动归方程:F[t][now] = max(add_cool + f[t-1][k], f[t][now])

    其中now是这一时刻按死的按键,pre是上一时刻必须按死的按键,k是所有包含pre的有效按键。

    下面是一些优化细节:

1、  首先先对所有按键状态做一次预处理,用conflict[state]表示state这个按键组合是否会产生冲突,这样动归的时候可以方便判断是否产生冲突。

2、  预处理每一秒所有得分按键的组合total[t],当动态规划到时间t的时候,若枚举的按键state不包含在total[t]内也直接忽略过去(这个预处理去掉就TLE了……)

3、  时间t,枚举每个按键的时候,即处理f[t][state]时,在考察这么按可以增加多少个cool的同时:处理一下如此按键上一秒的必须按键,即哪一些键在上一秒必须按死,记为pre;处理一下这一时刻必须按死的键,记为now。因为作为single note的得分按键,对上一秒下一秒都没有影响,在不冲突的情况下得到cool就可以了。进而在枚举f[t][state]的前一秒按键k的时候,k显然必须包含pre,避免再进行判断之类。

在strip note这里其实还有一些细节需要处理。这一个细节导致了我的一次Wrong Answer。在枚举按键的时候,不妨应该将strip note的终点也暂时记为按下,但是不参与冲突按键的判断。否则枚举f[t][state]中的state时候,若strip note是放开的,无法判断是不要得分的放开,还是得分的放开。

 

小结:

    动态规划除了需要事先有一个严密的转移方程,像这种比较麻烦的题目许多细节也需要考虑进去。

    面对看似恐怖的时间复杂度(尤其是徘徊在TLE边缘的时间复杂度)不要退缩,有的时候一个小小的优化,譬如上述中total[t]的预处理就可以把程序从TLE带向AC。

 

代码:

 

hdu3229

 

posted on 2010-08-26 20:42 Dango 阅读(541) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理