P1029 骨牌铺方格 - 题解

登录注册上岸

以下题解仅供学习参考使用。

抄袭、复制题解，以达到刷AC率/AC数量或其他目的的行为，在N诺是严格禁止的。

N诺非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看N诺社区规则。

2024年4月23日 18:18

骨牌铺方格题解：

P1029

回复 0 | 赞 0 | 浏览 421

#include <iostream> #include <vector> using namespace std; int main(void){ int n; while(cin>>n){ if(n==0){ cout<<" "<<...

2024年3月22日 19:42

骨牌铺方格题解：dp

P1029

回复 0 | 赞 0 | 浏览 435

#include <stdio.h> #include <stdlib.h> int n; int dp[10000005]; int main() { dp[1]=1; dp[2]=2; dp[3]=4; while(scanf("%d",&n)!=EOF) { if(n==0)break; for(int i=4;i<=n;i++){ dp[i]=dp[i-1]+dp[i-2]+dp[i-3]; ...

2023年3月16日 11:47

递推的的原理--参考斐波那契数列原理

P1029

回复 0 | 赞 2 | 浏览 2.5k

我们根据它1*1为单位，那么则有两个1*1可以合并为一个1*2，三个1*1可以合并成一个1*3的方块的角度，我们可以得出以后类似的递推关系式，而且做这种一般规律题目我们都要想到借鉴我们的“老祖宗”——斐波那契数列同样是可以理解成抽象数据模型：再加进新的下一个方块之前，首先会保留原始的状态数量为基线，新的方块则作为一个1*1的方块进行插入；那么根据题意，一共只有三种方块形式：1*1、1*2、1*3；那么接下来就插入的方块就和前一个方块组成一个新的1*2方块看作整体，那么剩余方块就是n-2，进行新的组合添加进之前的基数之中，以此类推&m...

2020年7月12日 11:18

骨牌铺方格（找规律）

P1029

回复 0 | 赞 0 | 浏览 8.9k

//骨牌铺方格 (找规律) #include<iostream> using namespace std; int sum(int n); long long rem[1024] = {0}; int main(){ int n,scheme; cin >> n; while(n){ scheme = sum(n); cout << scheme << endl; cin >> n; } return 0; } int sum(int n){ int res =...

2020年3月24日 10:27

骨牌铺方格（c++）

P1029

回复 0 | 赞 0 | 浏览 10.3k

经分析，本题存在递推公式：dp[i] = dp[i-1] + dp[i-2] + dp[i-3]; 初始值：dp[1] = 1, dp[2] = 2, dp[3] = 4; 注意使用数据类型long long 可以通过剪枝来降低时间复杂度 #include<iostream> #include<cstring> using namespace std; int main() { int n; long long dp[5000]; memset(dp, 0, sizeof(dp)); dp[1] = 1, dp[...

2020年2月23日 18:42

题解：骨牌铺方格

P1029

回复 0 | 赞 3 | 浏览 11.7k

有一排格子，我们从左向右码放骨牌。由于当前可以码放的骨牌是由前一格或者前两格或者前三格的码放方式决定。那么可以得出来公式：F(n)=F(n-1)+f(n-2)+f(n-3)（变种斐波那契数列？）且F(1)=1,F(2)=2,F(3)=4 那么很容易写出递归代码，这里还用了记忆搜索算法，就是定义一个用来记答案的数组remember[]，用来避免重复计算某一F(n)而导致效率很慢 #include<iostream> using namespace std; long long remember[1024]; long long f(...

题目骨牌铺方格

题解数量6

热门题解

1 题解：骨牌铺方格

2 递推的的原理--参考斐波那契数列原理

3 骨牌铺方格（c++）

4 骨牌铺方格题解：dp

5 骨牌铺方格题解：

6 骨牌铺方格（找规律）