[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