首页 > 试题广场 > 牛牛铺地毯
[编程题]牛牛铺地毯
  • 热度指数:1781 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 128M,其他语言256M
  • 算法知识视频讲解
牛牛有一块"2*n"的空白瓷砖并且有足够多的"1*2"和"2*3"两种类型的地毯(地毯可以旋转).现在他想在满足以下条件: 地毯之间不能相互重叠,地毯不能铺出瓷砖外以及不能有空隙下铺满整个瓷砖.问你一共有多少种不同的方案并且结果模上10007输出.

进阶:时间复杂度,空间复杂度

输入描述:
第一行输入一个正整数 T .表示有 T 组数据.
接下来 T 行,每行输入一个正整数 n.
1<= T <= 100
1<= n <= 100000


输出描述:
输出 T 行,每一行对应每组数据的输出.
示例1

输入

4
1
2
3
5

输出

1
2
4
13
要么1*2横着放,要么1*2竖着放,要么放一个2*3的。横着放则必须再来一块补一下下边就形成了2*2的一个整体,所以要么1*2竖着放,要么2*2的一个大整体,要么2*3的大整体,就这三种。竖着看2*2占两个竖排,2*3占3个竖排,就相当于青蛙跳台阶一次可以跳1,2,3个台阶。这样最后一次要么是1*2竖着放(1个台阶)要么2*2大整体(2个台阶)要么2*3(3个台阶)。所以f(n)=f(n-1)+f(n-2)+f(n-3);再算出当n为1时有几种放法,n为2几种放法,n为3几种放法,然后利用上面的方程就能算出
发表于 2022-03-26 17:45:44 回复(0)
很典型的动态规划问题,但我属于看出来这个的题型但是不知道该咋做的菜鸡。。。参考了百度出来的c++解法才理解的。设共有f(n)种情况,如果我们先横着放一块1*2的地毯时剩下的情况是f(n-1),如果我们先竖着放一块1*2的地毯时剩下的情况是f(n-2),如果先放上一块2*3的地毯时剩下的情况是是f(n-3)。即f(n) = f(n-1)+ f(n-2)+ f(n-3)。也就等同于青蛙跳台阶有三种跳法,跳1阶、跳2阶、跳3阶的情况。
这里写递归的话会超时,因此直接用dp来做:
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        //已知最大值为100000,则初始化一个长度为100001的数组
        int[] dp = new int[100001];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;
        //计算出所有情况,记得模上10007
        for(int i = 4; i < 100001; i++){
            dp[i] = (dp[i - 1] + dp[i - 2] + dp[i - 3])%10007;
        }
        //获取输入的值
        Scanner scanner = new Scanner(System.in);
        while(scanner.hasNext()){
            int nums = scanner.nextInt();
            for(int i = 0; i < nums; i++){
                System.out.println(dp[scanner.nextInt()]);
            }
        }
    }
}

发表于 2021-02-12 22:05:58 回复(11)
JS V8
说实话...牛客网这个输入规则真有点打脑壳(可能是因为我比较菜吧
看题解都没有JS的,补一个
//先接收第一行作为数组长度
const lineNum = parseInt(readline());
let arr = [];
for(let i = 0; i < lineNum; i++){
    //readline()这个函数每次调用都会读取下一行输入
    let line = readline();
    arr.push(Number(line))
}
const niuNiu = (n) => {
    const dp = new Array(n).fill(0);
    //初始化dp数组。这部分自己画下图就想明白了。分别代表2*1,2*2,2*3时的铺法数量
    dp[0] = 1;
    dp[1] = 2;
    dp[2] = 4;
    for(let i = 3; i < n; i++){
        dp[i] = (dp[i - 1] + dp[i - 2] + dp[i - 3]) % 10007;
    }
    //这里注意不是n
    return dp[n - 1];
}
for(let x of arr){
    console.log(niuNiu(x));
}


发表于 2022-03-18 07:00:45 回复(2)
/**
 *      author:刷完这题就去睡觉
 *      created:
**/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=100100;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin>>T;
    while(T--){
        int n;
        cin>>n;
        int dp[maxn]={0};
        dp[1]=1;
        dp[2]=2;
        dp[3]=4;
        for(int i=4;i<=n;i++){
            dp[i]=dp[i-1]+dp[i-2]+dp[i-3];
            dp[i]%=10007;
        }
    cout<<dp[n]<<endl;
    }
    return 0;
}

发表于 2021-08-11 15:51:55 回复(0)
枚举了前五个之后发现了规律 f(n) = f(n - 1) + f(n - 2) + f(n - 3);大胆猜测这个就是结果,之后 dp 即可,也可以使用三个变量迭代,不清楚牛客的评测规则,选择了数组记忆化存储;
import java.util.Scanner;
public class Main {
    static int mod = 10007;
    // 列举前五个数字后发现
    // 1 --> 1
    // 2 --> 2
    // 3 --> 4
    // 4 --> 1 + 2 + 4 = 7
    // 5 --> 2 + 4 + 7 = 13
    // 大胆猜想:f(n) = f(n - 1) + f(n - 2) + f(n - 3);
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        int[] dp = new int[100005];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;
        while (t-- != 0) {
            int n = sc.nextInt();
            if (dp[n] != 0) {
                System.out.println(dp[n]);
                continue;
            }
            for (int i = 4; i <= n; ++i) {
                dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
                dp[i] %= mod;
            }
            System.out.println(dp[n]);
        }
    }
}


发表于 2022-08-24 06:55:56 回复(0)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <stdio.h>
intmain(){
    intT;
    inta[100];
    scanf("%d",&T);
    for(inti = 0; i<T; i++){
        scanf("%d",&a[i]);
    }
    intnum[100000];
    num[1] = 1;
    num[2] = 2;
    num[3] = 4;
    for(inti=4; i<=100000; i++){
        num[i]= num[i-1] + num[i-2] + num[i-3];
        num[i] %= 10007;
    }
    for(inti=0; i<T; i++){
        printf("%d\n",num[a[i]]);
    }
}
发表于 2022-03-31 23:00:58 回复(2)
#include<bits/stdc++.h>
using namespace std;
int res[100000];
int main(){
    int T;
    cin >> T;
    res[0] = 1;
    res[1] = 2;
    res[2] = 4;
    for(int i = 3; i < 100000; i++){
        res[i] = res[i - 1] + res[i - 2] + res[i - 3];
        res[i] %= 10007;
    }
    for(int i = 0; i < T; i++){
        int n;
        cin >> n;
        cout << res[n - 1] << '\n';
    }
        
}

发表于 2021-09-17 09:49:01 回复(0)
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int T=sc.nextInt();
        int[] temp=new int[T];
        for(int i=0;i<T;i++){
        temp[i]=sc.nextInt();
        }
        for(int i=0;i<T;i++){
            System.out.println(count(temp[i]));
        }
    }
    public static int count(int a){
        if(a==1){return 1;}
        if(a==2){return 2;}
        if(a==3){return 4;}
        int one=1;int two=2;int three=4;int res=0;
        for(int i=4;i<a+1;i++){
         res=(one+two+three)%10007;
            one=two;two=three;three=res; 
        }
        return res; 
    }
}

发表于 2021-08-21 10:55:04 回复(0)
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * @author tanglei
 * @create 2021-08-20 21:49
 */
public class ditan {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] dp = new int[100001];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;

        for (int i = 4; i < 100001; i++) {
            dp[i] = (dp[i - 1] + dp[i - 2] + dp[i - 3]) % 10007;
        }

        while (sc.hasNextInt()) {
//            int n = sc.nextInt();
           int a = sc.nextInt();
           int[] b = new int[a];
            for (int i = 0; i < a; i++) {
                b[i] = sc.nextInt();
                System.out.println(dp[b[i]]);
            }
        }
    }
}

发表于 2021-08-20 23:43:01 回复(0)