CF232C Doe Graphs
一看到题第一时间想到的大概是点的个数满足斐波那契数列的关系，即\(fib_i=fib_{i-1}+fib_{i-2}\)，在题目中可以得知\(fib_{0}=1,fib_{1}=2\)（这里的\(fib_{i}\)即为文中的\(D_{i}\)）
然后考虑怎么求第n次的i到j的距离呢？自然想到这可能和上一次有关系，那么有什么关系呢？我们自然而然想到了递推（不习惯用f，这里用dp取代）
设\(dp_{n,i,j}\)表示第n层，从i到j至少需要走的路径长度，然后考虑它怎么转移
下面分三种情况：
- \(i,j≤fib_{n-1}\)，即两个点都在第\(n-1\)的图上，这时候考虑\(dp_{n,i,j}\)等于什么，显然得出\(dp_{n,i,j}=min{dp_{n-1,i,j}\) //即直接从这两个点走，不经过第n层新增的点
\(,min{dp_{n-1,1,i}+dp_{n-1,j,fib_{n-1}}+2,dp_{n-1,i,fib_{n-1}}+dp_{n-1,1,j}+2}\) //即经过新加的\(1,fib_{n-1}+1\)和\(fib_{n-1},fib_{n-1}+1\)的边
- \(i≤fib_{n-1},j>fib_{n-1}\) 可以试想把j移到j-fib_{n-1}的位置，即原图形的镜像位置（莫名皇室）
这个玩意儿愿读者自行画图理解那么它经历什么呢，显然是\(min{dp_{n-1,1,i},dp_{n-1,i,fib_{n-1}}}\) //即i点到1或者$fib_{n-1}的距离
+dp_{n-2,1,j-fib_{n-1}}+1 //即j点到1点的距离
若i,j相反则swap一下即可
- \(i>fib_{n-1},j>fib_{n-1}\) 其实此时的位置就相当于它与第\(n-1\)层的镜面位置
\(dp_{n,i,j}=dp_{n-2,i-fib_{n-1},j-fib_{n-1}}\)
此时处理好了dp，如果你这是以为大功告成了，那我告诉你你想多了