Kattis - honey【DP】

题意

有一只蜜蜂，在它的蜂房当中，蜂房是正六边形的，然后它要出去，但是它只能走N步，第N步的时候要回到起点，给出N， 求方案总数

思路

用DP 因为N == 14

所以 最多走7步 我们不妨设 (7, 7) 为原点，然后 dp[0][7][7] = 1

因为 N == 0 的时候 方案数只有一个 那就是 不动吧。。

dp[i][j][k] i 代表第几步 j k 分别表示 目前的位置

一个点 在一张图里面本来有八个方向可以走

这里六边形 我们只取六个方向就可以

AC代码

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cmath>

#include <deque>

#include <vector>

#include <queue>

#include <string>

#include <cstring>

#include <map>

#include <stack>

#include <set>

#include <cstdlib>

#include <ctype.h>

#include <numeric>

#include <sstream>

using namespace std;

typedef long long LL;

const double PI  = 3.14159265358979323846264338327;

const double E   = 2.718281828459;

const double eps = 1e-6;

const int MAXN   = 0x3f3f3f3f;

const int MINN   = 0xc0c0c0c0;

const int maxn   = 1e5 + 5;

const int MOD    = 1e9 + 7;

int dp[30][30][30];

int Move[6][2] =

{

    1, 0,

    0, 1,

   -1, 0,

    0,-1,

    1, 1,

   -1,-1,

};

int main()

{

    int i, j, k, l;

    memset(dp, 0, sizeof(dp));

    dp[0][7][7] = 1;

    for (i = 1; i <= 14; i++)

    {

        for (j = 0; j <= 14; j++)

        {

            for (k = 0; k <= 14; k++)

            {

                for (l = 0; l < 6; l++)

                {

                    dp[i][j][k] += dp[i - 1][j + Move[l][0]][k + Move[l][1]];

                }

            }

        }

    }

    int t;

    cin >> t;

    while (t--)

    {

        int n;

        scanf("%d", &n);

        printf("%d\n", dp[n][7][7]);

    }

}