HDU 6146 Pokémon GO （dp）

HDU 6146 Pokémon GO （dp）

Description

Input

第一行为T，表示输入数据组数。每组数据包含一个数N。1≤T≤1001≤N≤10000

Output

对每组数据输出方案数目，结果对 1 000 000 007 取模。

Sample Input

3123

Sample Output

22496

思路

显然，步数最少的方案当然是所有格子只访问一遍咯！

我们设 Bn

显然：

B1=1

Bn=2×Bn−1=2n−1

同样，我们设 An

则 An=Bn+2×An−1+4×An−2

其中 Bn 代表回到了当前列的方案数， An−1 代表先填满当前列然后走到相邻的列处理同样的一个子问题， An−2 代表通过对角线方式先走完当前列与相邻列的格子，然后剩下的 n−2

因为有四个角，所以我们的结果要乘以 4 ，即 4×An

当然，真实情况下我们不一定是从四个角出发的，还有另一种情况就是中间的列咯。

考虑中间的第 i

我们可以先从第 i

也可以先往右走完所有的格子回来，再往左走完所有的格子。于是总的方案数即 2×(4×Bi−1×An−i+4×Bn−i×Ai−1) ，其中 2 代表第 i 列有两个格子可选为初始点， 4 代表分别向左右两边行走时的选择方案数 2×2 AC 代码#includetypedef long long LL;using namespace std;const int maxn =1e5+10;const int mod = 1e9+7;LL a[maxn],b[maxn];void init(){ b[1]=1; for (int i=2; i>T; while(T--) { int n; cin>>n; if(n==1) { cout<<2<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。