为防止广告，目前nocow只有登录用户能够创建新页面。如要创建页面请先登录/注册（新用户需要等待1个小时才能正常使用该功能）。
USACO/vans
这篇文章可以证实是由NOCOW用户原创，不存在任何版权争议。 本文作者同意以GNU FDL、CC-by-sa和GNU LGPL（如果适用）三种版权发布此文章（不包括翻译文章中属于原始所有者的部分版权）。 如果你修改了这篇文章并且不同意用GNU FDL以外的版权发布，可以换一个版权模板或者移除此模板。
- 这是USACO Chapter 6 .1中的OI题目Postal Vans的介绍及题解，参见 翻译，C语言代码，C++语言代码，Pascal语言代码。
目录 |
[编辑] 问题分析
诡异算法 by Maigo（至今不知道原理是什么）： 设a[i]表示第i列的左上和左下角有直线连通时的路径数，b[i]表示第i列的左上和左下角没有直线连通时的路径数，则有： b[i]:=a[i-1]+b[i-1]; a[i]=2+a[i-2]+2(a[i-2]+b[i-2]+a[i-1]+b[i-1]+...) =2+a[i-2]+2(b[i-1]+b[i-2]+...) 其中a[i]的值可以在计算过程中累加。 这样算法的时间复杂度仅为O(n)。加上高精度运算也能轻松通过。
在这再加一些 来自BillyLinux大牛{http://billylinux.blog.hexun.com/10542440_d.html} 这一题可以用DP解决：
考虑到要经过每一个点，那么对于最后形成的路，每一竖条横向的路不是4条就是2条，总共8种（不考虑路径方向）：
1 2 3 4 5 6 7 8 — — — — — — — — — — — — — — — — — — — —
（7中最上面的与最下面的相连、8中最上面的与第二个相连）
并且对于经过最后面的4个点，路径形状只可能是两种（3、8），于是我们定义两个状态
a[i]——有i竖条，以3号形状结尾的路径数
b[i]——有i竖条，以8号形状结尾的路径数
例如：对于i=3：
a[3]=2 b[3]=2
接下来的问题，就是如何进行状态转移：
我们考虑下面的几种情况：
对于a[i]，它可以接在a[i-2]、a[i-3]……与b[i-2]、b[i-3]……上（这里的接上，指的是中间不出现3号与8号路径），并且除了a[i-2]以外，其他都有两种接法（a[i-2]有3种），因此经过分类，我们可以得到：
a[i]=2*(a[i-2]+a[i-3]+……+a[2]+b[i-2]+b[i-3]+……+b[2]+1)+a[i-2]
而对于b[i],不难发现，他只能接在a[i-1]与b[i-1]上，因此有
b[i]=a[i-1]+b[i-1]
于是我们可以将a[i]化简为
a[i]=a[i-2]+2+2*(b[i-1]+b[i-2]+……b[3])
至此问题大致解决，另外需要注意的是要用高精度。
这里是我写的一份详细的题解，由于里面图很多，所以不便贴在这里~~好心的管理员帮忙吧！
http://www.oibh.org/bbs/thread-16548-1-1.html(提醒：已经404)
补充一个本题的递推式(by curimit)：
n≥5时，有如下的递推关系： f(n)=2f(n-1)+2f(n-2)-2f(n-3)+f(n-4)
初值： f（1）=0，f（2）=2，f（3）=4，f（4）=12
从第5项开始向后推即可。
关于上面递推式的求解方法(by Tearhap_断章):
求环路总数量等价于求起点(1,1)终点(2,1)的哈密顿路的数量*2（定义点（2,1）在（1,1）下方）
定义f[i]为i*4矩阵中(1,1)→(2,1)哈密顿路的数量
g[i]为i*4矩阵中(1,1)→(4,2)的哈密顿路数量
则f[i]=f[i-1]+g[i-1] （画画图感受一下）
然后讨论第一列点的走入走出方式（共4种，画画图）可以算出
g[i]=g1[i]+g2[i]+g3[i]+g4[i]=g[i-2]+2*f[i-1]+g[i-1]-g[i-3]
把g用f[i]-f[i-1]代进去 解函数方程
可得到以上的f[n]=2f[n-1]+2f[n-2]-2f[n-3]+f[n-4]的结论 --CD：更极品的是算出递推式的通项式，O(高精度计算)！
回LS，通项式不好说了。。不过矩阵本菜倒是推了个。。 (f1 f2 f3 f4)*矩阵=(f2 f3 f4 f5) 然后用快速幂加速就ok，下面是矩阵。。
0 0 0 1
1 0 0 -2
0 1 0 2
0 0 1 2
By SongS
很明显，这个题目也可以用基于连通性的状态压缩动态规划来做，有兴趣的可以练习练习。 很诡异啊，我用URAL1519的AC代码搞，竟然在N=30全部爆0....
[编辑] 详细的题解
精心制作了一份：————pty http://www.docin.com/p-94253938.html
[编辑] 另外一种方法
见5.4.4题解，至少这个方法勉强能过吧
贴下运行时间
USER: ****** [y1y2t341] TASK: vans LANG: C Compiling... Compile: OK Executing... Test 1: TEST OK [0.011 secs, 9644 KB] Test 2: TEST OK [0.011 secs, 9644 KB] Test 3: TEST OK [0.011 secs, 9644 KB] Test 4: TEST OK [0.000 secs, 9644 KB] Test 5: TEST OK [0.011 secs, 9644 KB] Test 6: TEST OK [0.032 secs, 9644 KB] Test 7: TEST OK [0.043 secs, 9644 KB] Test 8: TEST OK [0.076 secs, 9644 KB] Test 9: TEST OK [0.259 secs, 9644 KB] Test 10: TEST OK [0.443 secs, 9644 KB] Test 11: TEST OK [0.907 secs, 9644 KB]
还有，可以预处理转移方案，但是我还没加上去就AC了
路人m：没看到上面的“很明显，这个题目也可以用基于连通性的状态压缩动态规划来做，有兴趣的可以练习练习。 很诡异啊，我用URAL1519的AC代码搞，竟然在N=30全部爆0....”吗？
1
