NCPC 2006 I - Honeycomb Walk

回来水文了
本来一道好好的DP大水题 训练赛活活做成找规律 结果最后一个半小时AFK

NCPC 2006 I - Honeycomb Walk
Kattis - honey
POJ 3036 - Honeycomb Walk

1.png

大致题意是有只小蜜蜂 飞在花丛中:)
蜜蜂会走N步(1<=N<=14) 在N步之后蜜蜂会回到初始的起点 求当蜜蜂可以走N步的时候 有多少种走法

首先蜂巢是典型的六边形排列
使用数组模拟蜂巢的排列(取一点的左,左上,上,右,右下,下六个点模拟 bug大佬想到了结构体建边2333333暴力搜索打表)
之后对于点(x,y)在第k步可以走到的走法基于上一步周围六个点的状态
可以推出F(x,y,k)=F(x-1,y,k-1)+F(x-1,y-1,k-1)+F(x,y-1,k-1)+F(x+1,y,k-1)+F(x+1,y+1,k-1)+F(x,y+1,k-1)
直接打个表就过了 一道大水题QwQ 如果比赛真出这种题踩坑了怕不是要后悔一辈子

Accept 2/2 C++ 2ms 3MB:

/**
 * @author    Moe_Sakiya        i@tun.moe
 * @date    2018-04-25 14:34:47
 *
 */

#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <queue>

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>

using namespace std;

int t, n;

//对于点x,y来说在第n步的最大路径数
int dparr[30][30][15];

void calDP(void) {
    int i, j, k;
    //init
    dparr[15][15][0] = 1;
    for(k = 1; k <= 14; k++)
        for(i = 1; i <= 29; i++)
            for(j = 1; j <= 29; j++)
                dparr[i][j][k] = dparr[i][j - 1][k - 1] + dparr[i - 1][j - 1][k - 1] + dparr[i-1][j][k - 1] + dparr[i][j + 1][k - 1] + dparr[i + 1][j + 1][k - 1] + dparr[i + 1][j][k - 1];
    return;
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    calDP();
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        printf("%d\n", dparr[15][15][n]);
    }
    return 0;
}

添加新评论

captcha
请输入验证码