首页 > 试题广场 > 牛牛铺地毯
[编程题]牛牛铺地毯
  • 热度指数:885 时间限制: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
很典型的动态规划问题,但我属于看出来这个的题型但是不知道该咋做的菜鸡。。。参考了百度出来的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 回复(1)
#include<stdio.h>
#define S(a) scanf("%d",&(a))
#define F(a,b) for(i=a;i<b;i++) 
int main(){
    int T,num[101],m,n[100001]={1,2,4},i;
    S(T);
    F(0,T) S(num[i])?num[i]>m?m=num[i]:0:0;
    F(3,m) n[i]=(n[i-1]+n[i-2]+n[i-3])%10007;
    F(0,T) printf("%d\n",n[num[i]-1]);
    return 0;
}
发表于 2021-04-01 00:27:18 回复(0)
#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)
/**
 *      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)