首页 > 试题广场 >

牛牛铺地毯

[编程题]牛牛铺地毯

热度指数：1988 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 128M，其他语言256M
算法知识视频讲解

牛牛有一块"2*n"的空白瓷砖并且有足够多的"1*2"和"2*3"两种类型的地毯(地毯可以旋转).现在他想在满足以下条件: 地毯之间不能相互重叠,地毯不能铺出瓷砖外以及不能有空隙下铺满整个瓷砖.问你一共有多少种不同的方案并且结果模上10007输出.

进阶：时间复杂度 $O(n)\$ ，空间复杂度 $O(n)\$

输入描述:

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

输出描述:

输出 T 行,每一行对应每组数据的输出.

示例1

输入

输出

算法知识视频讲解

牛客306634497号

很典型的动态规划问题，但我属于看出来这个的题型但是不知道该咋做的菜鸡。。。参考了百度出来的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 回复(12)

马保国记名弟子

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)

每天不断自我拉扯

要么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)

刷完这题我就去睡觉

/**
 *      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)

Xbai-hang

枚举了前五个之后发现了规律 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)

Lok记得你

C#，DP，用字典减少计算量，即遇到更大的数计算它与当前最大之间的所有数并存入字典

using System;
using System.Collections.Generic;
namespace text
{
    public class Program {
        public static void Main() {
            // string line;
            // while ((line = System.Console.ReadLine ()) != null) { // 注意 while 处理多个 case
            //     string[] tokens = line.Split();
            //     System.Console.WriteLine(int.Parse(tokens[0]) + int.Parse(tokens[1]));
            // }
            int row = int.Parse(System.Console.ReadLine());
            List<int> datalist = new List<int>();//原始数据
            List<int> ans = new List<int>();//输出
            Dictionary<int, int> _dic = new Dictionary<int,int>(); //字典用于减少计算量           
            _dic.Add(1, 1);
            _dic.Add(2, 2);
            _dic.Add(3, 4);
            int currmax = 3;//当前计算到的最大数
            int Mod = 10007;
            while(row-- > 0)
            {
                datalist.Add(int.Parse(System.Console.ReadLine()));
            }

            for(int i = 0; i < datalist.Count; i++)
            {
                while(currmax < datalist[i])//如果第i位大于计算过的最大数，则计算最大数到第i位的所有数并存入字典
                {
                   _dic.Add(currmax + 1, ((_dic[currmax] + _dic[currmax - 1] + _dic[currmax - 2]))%Mod);
                    currmax++;
                }
                ans.Add(_dic[datalist[i]]);
            }
            foreach(var a in ans)
            {
                System.Console.WriteLine(a);
            }
        }
    }
}

发表于 2023-05-19 10:08:40 回复(0)

上理之光

#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)

牛客681574814号

#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)

牛客633037634号

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)

buyghrwiyu

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)

提交观点

问题信息

C++工程师 iOS工程师安卓工程师运维工程师前端工程师算法工程师网易游戏研发工程师 2021

上传者：小小

难度：

10条回答 197收藏 5171浏览

通过挑战的用户

牛客49959...

2023-02-27 14:57:44
QLLQL

2023-02-21 20:11:11
牛客62533...

2022-11-15 22:53:00
牛客60422...

2022-11-13 13:27:53
牛客38827...

2022-11-11 16:22:16

牛牛铺地毯

输入描述:

输出描述:

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题