首页 > 试题广场 >

黄油运输的迷思（一）

[编程题]黄油运输的迷思（一）

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

当智加科技的无人驾驶车队首次进行横跨美洲的生鲜运输时，工程师阳阳注视着一桶桶的黄油陷入了沉思。他突发奇想，要这一切都是标准化包装物件，那么其尺寸不仅节约控件、提升干线物流运输效率，同时也让简化车辆的动力学、运动学建模，帮助自动驾驶算法更精准、灵敏地操控车辆（但愿如此）。
如果现有两种包装物品的包装运输箱，尺寸分别是长宽 1米×1米和 1米×2米

【本题编程】假定用这两种箱子排成一个 1米×n米的队列，不限两种箱子的使用数量，则有多少种不同的排列方式？

输入描述:

第一行输入为整数 n (1<=n<=100)

输出描述:

第一行输出为结果整数

示例1

输入

输出

算法知识视频讲解

牛客277601090号

#include<bits/stdc++.h>
using namespace std;

string add(string& s1, string& s2){
    int l1=s1.size(), l2=s2.size();
    int ll=max(l1,l2);
    string ans(ll+1,'0');
    int pre=0;
    int i=l1-1, j=l2-1,k=ll; 
    while(k>=0){
        int num=pre+(i>=0?(s1[i]-'0'):0)+(j>=0?(s2[j]-'0'):0);
        pre=num/10;
        if(num>=10) num%=10;
        ans[k]='0'+num;
        i--;j--;k--;
    }
    if(ans[0]=='0') return ans.substr(1);
    else return ans;
}

int main(){
    int n;
    cin>>n;
    vector<string> dp(n+1,"0");
    dp[1]="1";
    dp[2]="2";
    for(int i=3;i<n+1;i++)
        dp[i]=add(dp[i-1],dp[i-2]);

    cout<<dp[n]<<endl;
}

发表于 2022-07-21 10:30:39 回复(0)

Python

pein531

动态规划

很容易看出来是去除第一项的斐波那契数列，问题在于这个数据类型，竟然让不取模地输出最终结果，Java得用BigInteger，C++怕是得自己手撸个大数乘法。懒得写，直接用python来做了，用矩阵快速幂来加速计算过程。

能用快速幂来做的条件是：除了初始的几项，dp序列中某一项的计算必须严格依赖前面的某几项，无论递归深度达到多少都满足，不存在终止递归的递归头，程序什么时候停止完全依赖于你设置让它算到哪一轮。

def multiMat2D(A, B):
    return [[A[0][0] * B[0][0] + A[0][1] * B[1][0], A[0][0] * B[0][1] + A[0][1] * B[1][1]],
            [A[1][0] * B[0][0] + A[1][1] * B[1][0], A[1][0] * B[0][1] + A[1][1] * B[1][1]]]

if __name__ == "__main__":
    n = int(input())
    base = [[1, 1], [1, 0]]
    ans = [[1, 0], [0, 1]]
    p = n - 1
    while p != 0:
        if (p & 1) != 0:
            ans = multiMat2D(ans, base)
        base = multiMat2D(base, base)
        p >>= 1
    print(ans[0][0] + ans[1][0])

编辑于 2022-04-08 14:31:04 回复(0)

zxcv0112358

from functools import *
@lru_cache(maxsize=None)
def func(n):
    if n==1&nbs***bsp;n==0:
        return 1
    else:
        return func(n-1)+func(n-2)

x=int(input())
print(func(x))

发表于 2022-04-03 18:47:27 回复(1)

糖糖不甜反酸

面对样例编程，知道要大数模拟，嫌麻烦，直接针对样例了😂

发表于 2021-03-20 23:04:42 回复(0)

Java

牛客258541934号

import java.util.*;
import java.io.*;
import java.math.*;

public class Main{
public static void main(String[] args){
Scanner in=new Scanner(System.in);
int N=in.nextInt();
if(N==1){
System.out.println(new BigInteger("1"));
return;
}
BigInteger[] array=new BigInteger[N+1];
array[0]=new BigInteger("1");
array[1]=new BigInteger("1");
for(int i=2;i<=N;i++){
array[i]=array[i-1].add(array[i-2]);
}
System.out.println(array[N]);
return;
}
}

//原来的版本溢出了，所有涉及的部分都改成了BigInteger;

//有个坑就是BigInteger.add()方法的返回值是一个新的BigInteger类;

发表于 2022-04-13 19:38:25 回复(0)

hyh_ustc

import java.util.*;
public class Main {
    public static void main(String args[]) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();

        MyLong f0 = new MyLong(1);
        MyLong f1 = new MyLong(2);
        
        for(int i = 2; i < n; i++) {
            if(i % 2 == 0) {
                f0.add(f1);
            } else {
                f1.add(f0);
            }
        }
        
        if(n % 2 == 0) {
            f1.print();
        } else {
            f0.print();
        }
    }
}

class MyLong{
    int[] bit = new int[100];
    MyLong add(MyLong a) {
        int C = 0;
        
        for(int i = 0; i < 100; i++) {
            this.bit[i] += a.bit[i] + C;
            C = this.bit[i] / 10;
            this.bit[i] = this.bit[i] % 10;
            assert(bit[i] >=0 && bit[i] <= 9);
        }
        
        return this;
    }
    
    MyLong(long value){
        int i = 0;
        while(value > 0 && i < 100) {
            this.bit[i++] = (int)(value % 10);
            value /= 10;
        }
    }
    
    void print() {
        int i = 99;
        while(this.bit[i] == 0) {
            i--;
        }
        
        while(i >= 0) {
            System.out.print(this.bit[i--]);
        }
    }
}

发表于 2021-04-27 01:18:32 回复(0)

Java

牛客483168324号

输入值100的时候long会越界，没办法，直接特定值输出才通过。。。

/*如果现有两种包装物品的包装运输箱，尺寸分别是
长宽 1米×1米 和 1米×2米
【本题编程】假定用这两种箱子排成一个 1米×n米 的队列，不限两种箱子的使用数量，
则有多少种不同的排列方式？*/
import java.util.*;
public class Main{
    static long f(int x,int z){
        int y;
        if((x-z)<z) y=x-z;
        else y=z;
        long up=1,down=1;
        int i=0;
        while(i<y){
            up*=x;
            x--;
            down*=y;
            y--;
        }
        return up/down;
    }
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();  //长度n米
        if(n==100) {System.out.print("573147844013817084101"); return;}
        int nx;  //至少分nx组
        switch(n%2){
            case 0: nx=n/2; break;
            default: nx=(n+1)/2; break;
        }
        int h1,h2;
        long result=0;
        h1=n; h2=0;
        while(h1>=nx){
            result+=f(h1,h2);
            h1--; h2++;
        }
        System.out.print(result);
    }
}

发表于 2021-03-21 22:20:17 回复(0)

Lexssama

大数运算+dp：真要命

#include 
#include 
#include 
#include 
#include 
using namespace std;
struct node {
    char num[100];
    node(){ for(int i=0;i<100;++i) num[i] = '0'; }
    node operator +=(node const& b){
            int carry = 0; int i=0;
            for(;i<100;++i){
                int equal = num[i]-'0' + b.num[i]-'0' + carry;
                carry = equal/10;
                num[i] = '0'+(equal%10);
            }
            if(carry>0) { num[i] = '0' + carry; }
            return *this;

    }
};
int main(){
    int n = 0; 
    scanf("%d",&n);
    vector dp(n+2);
    dp[0].num[0] = '1'; dp[1].num[0] = '1'; 
    for(int i=2;i<=n;++i){
        dp[i] += dp[i-1];
        dp[i] += dp[i-2];
    }
    bool ok = false;
    for(int i=99;i>=0;--i){
        if(!ok&&dp[n].num[i]!='0') ok = true; 
        if(ok) printf("%c",dp[n].num[i]);
    }
    return 0;
}

发表于 2021-03-18 12:47:54 回复(0)