[NOI2009 day2 管道取珠]动态规划、巧妙转化**

【题目】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1566

【算法分析】

这个是看了beyondvoid大牛才会得。。。关键在第一步转化。

首先,Ai^2可以看成对于相同输出序列的结果中,进行一个N^2的枚举可得。

即:

假设Ai=n

那么

for (int i=1;i<=n;i++)

for (int j=1;j<=n;j++) ans++;

得出的ans就是Ai^2

所以就相当于走两个相同输出序列的方案数。

这样的话:

用f[x1,y1,x2,y2]表示X状态走到(x1,y1),Y状态走到(x2,y2),它们之前走的输出序列是相同的这种情况下的方案数。

((x1,y1)表示上面已经弹了x1颗珠子出来,下面已经弹出了y1颗珠子出来。)

所以有

f[x1,y1,x2,y2]=以下各项之和。

f[x1-1,y1,x2-1,y2]      前提是(u[x1]==u[x2])

f[x1-1,y1,x2,y2-1]      前提是(u[x1]==d[y2])

f[x1,y1-1,x2-1,y2]      前提是(d[y1]==u[x2])

f[x1,y1-1,x2,y2-1]      前提是(d[y1]==d[y2])

然后初始值f[0,0,0,0]=1

然后这样由于空间太吓人了,而状态X和状态Y是同步运动的,我们可以通过x1+y1-x2算出y2,于是就把第四维略去了。

三维的空间本来是可以过了,然后由于这个题库太犀利。。。数组开大了会变成system error,所以只得再搞一个滚动数组。然后没想到的是,位运算居然那么耗时,TLE掉了,然后我就先用变量把i&1和(i&1)^1存起来再做。至于里面呢,用减法代替取余是必须的,然后我看到用了好几次同一个f,每次j+1,k+1之流也许会变慢,于是我直接开指针把它表示出来。

【其它】不错,排到了第二。

Rank Run ID User Memory Time Language Code Length Submit Time 1 6774 moon5ckq 2088K 1029MS G++ 0.87K 2009-09-14 09:42:34 2 9615 edward_mj 2068K 1045MS G++ 1.42K 2010-02-19 01:16:37

【CODE】

#include

加入对话

2条评论

  1. 回复oimaster:Orz神牛的到来。。。我觉得第一步比较难想,做完的话不觉得什么,但是如果考场上要想出第一步转化,没碰过类似的真的挺难搞。。。YM神牛

留下评论

您的电子邮箱地址不会被公开。