GESP 1-4级 -- GESP 5-8级 -- CSP-J/S --

A46351. $奶牛散步从一个无限大的矩阵的中心点出发，一步只能向右走、向上走或向左走。恰好走N步且不经过已走的点共有多少种走法？输入一个数字，代表N,N<=1000输出输出有多少方案样例输入 2 样例输出 7$

填空题较难

知识点

动态规划递推路径计数

题目描述

奶牛散步 从一个无限大的矩阵的中心点出发，一步只能向右走、向上走或向左走。恰好走N步且不经过已走的点 共有多少种走法？ 输入 一个数字，代表N,N<=1000 输出 输出有多少方案 样例输入 2 样例输出 7

参考答案

#include<bits/stdc++.h>
using namespace std;
int n,a[1001],i;
int main()
{
    cin>>n;a[1]=3;a[2]=7;
    for(i=3;i<=n;i++)
       a[i]=(2*a[i-1]+a[i-2])%12345;
      cout<<a[n];
       return 0;
    } 
}

上一题下一题