一个长方体，长宽高分别为x,y,z，都为自然数。
现在要把若干个相同的长方体摆成高为N的一根柱形体。
每层摆1个，如果两种摆法的高度是一样的，则认为这两种摆法等价，所以每层只有三种摆法。
求一共有多少种摆法。
[编程题]长方体的摆放
设dp[i][j]为第i层，高度为j的方案数，那么第i+1层的高度为j+x j+y j+z的方案数都等于第i层的
方案数，所以可以得出递推式为：
dp[i+1][j+x]+=dp[i][j]
dp[i+1][j+y]+=dp[i][j]
dp[i+1][j+z]+=dp[i][j]
再把高度为n的方案数加起来得出总和即可。
代码为：
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int x=sc.nextInt();
int y=sc.nextInt();
int z=sc.nextInt();
int[][] dp=new int[200][400];
dp[1][x]=1;
dp[1][y]=1;
dp[1][z]=1;
for(int i=2;i<200;i++){
for(int j=0;j<300;j++){
dp[i][j+x]+=dp[i-1][j];
dp[i][j+y]+=dp[i-1][j];
dp[i][j+z]+=dp[i-1][j];
}
}
int sum=0;
for(int i=0;i<200;i++){
sum+=dp[i][n];
}
System.out.println(sum);
sc.close();
}
}
发表于 2019-07-28 10:34:42
回复(0)
递归求解，每次分别尝试以长、宽、高作为高度来摆放，只要剩余高度为0就表示生成了一种可行的方案
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
String[] params = br.readLine().split(" ");
int x = Integer.parseInt(params[0]);
int y = Integer.parseInt(params[1]);
int z = Integer.parseInt(params[2]);
System.out.println(dfs(x, y, z, n));
}
private static int dfs(int x, int y, int z, int rest) {
if(rest == 0) return 1; // rest为0，凑出了一种合法的方案
if(rest < 0) return 0; // rest小于0，当前摆放方案不合理
// 分别尝试x,y,z作为本层的高度
return dfs(x, y, z, rest - x) + dfs(x, y, z, rest - y) + dfs(x, y, z, rest - z);
}
}
编辑于 2021-12-07 11:15:59
回复(0)
C++简单递归
#include<iostream>
using namespace std;
int a, b, c;
int aim;
int key = 0;
void ceng(int aim)
{
if (aim > a)
{
ceng(aim - a);
}
if (aim > b)
{
ceng(aim - b);
}
if (aim > c)
{
ceng(aim - c);
}
if (aim == a || aim == b || aim == c)
{
key = key + 1;
}
if (aim < a && aim < b && aim < c)
return;
}
int main()
{
cin >> aim;
cin >> a >> b >> c;
ceng(aim);
cout << key;
}
发表于 2020-03-24 12:25:17
回复(0)
C语言基础简单递归实现
#include<stdio.h>
/*
* n：题目中的n
* now：当前高度
* x,y,z：长宽高
* */
int sumAll(int n,int now,int x,int y,int z){
int sum=0;
if(now+x==n){
sum++;
}
if(now+y==n){
sum++;
}
if(now+z==n){
sum++;
}
if(now+x<n){
sum=sum+sumAll(n,now+x,x,y,z);
}
if(now+y<n){
sum=sum+sumAll(n,now+y,x,y,z);
}
if(now+z<n){
sum=sum+sumAll(n,now+z,x,y,z);
}
return sum;
}
int main(){
int n;
scanf("%d",&n);
int x,y,z;
scanf("%d %d %d",&x,&y,&z);
int sum=sumAll(n,0,x,y,z);
printf("%d",sum);
return 0;
}
发表于 2020-02-26 10:39:51
回复(0)
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int n, a[3];
int res = 0;
void fun(int h)
{
if (h == n)
{
res++;
return;
}
if (h > n)
return;
for (int i = 0; i < 3; i++)
{
fun(h + a[i]);
}
}
int main()
{
cin >> n;
cin >> a[0] >> a[1] >> a[2];
sort(a, a + 3);
fun(0);
cout << res << endl;
getchar();
return 0;
}
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int n, a[3];
int res = 0;
void fun(int h)
{
if (h == n)
{
res++;
return;
}
if (h > n)
return;
for (int i = 0; i < 3; i++)
{
fun(h + a[i]);
}
}
int main()
{
cin >> n;
cin >> a[0] >> a[1] >> a[2];
sort(a, a + 3);
fun(0);
cout << res << endl;
getchar();
return 0;
}
发表于 2019-08-04 22:29:23
回复(2)
package main
import (
"bufio"
"os"
"strings"
"strconv"
"fmt"
)
func main() {
inputReader := bufio.NewReader(os.Stdin)
line0, _ := inputReader.ReadString('\n')
line0 = strings.Replace(line0, "\n", "", -1)
n, _ := strconv.Atoi(line0)
line1, _ := inputReader.ReadString('\n')
line1 = strings.Replace(line1, "\n", "", -1)
lines1 := strings.Split(line1, " ")
nums:=[]int{}
for _,s:=range lines1{
temp, _ := strconv.Atoi(s)
nums=append(nums, temp)
}
dp:=make([]int,n+1)
dp[0]=1
for i:=1;i<=n;i++{
for _,v:=range nums{
if i>=v{
dp[i]+=dp[i-v]
}
}
}
fmt.Print(dp[n])
}
发表于 2022-09-01 14:49:19
回复(0)
JS写的，内存超出限制，大佬们有空可以改改
var height =parseInt(readline());
var nums = readline();
var arr=nums.split(' ');
var s=[];
let a=[];
for(var i=0;i<arr.length;i++){
s.push(parseInt(arr[i]));
}
//console.log(s);
backUp(height,0,s,0);
console.log(a[a.length-1]);
function backUp(height,n,s,sum){
if(height<n){
return;
}
if(height===n){
sum++;
a.push(sum);
}
if(height>n){
for(var i=0;i<3;i++){
backUp(height,n+s[i],s,sum);
}
}
}
发表于 2021-10-09 17:51:23
回复(0)
这题我用递归加排列组合有点暴力地搞出来了😓估计数据一大就得炸。
先递归加剪枝，求出所有满足条件的长宽高的数量。
然后把长宽高排列一下顺序，用A(a+b+c) / {A(a)*A(b)*A(c)} 就得出所有摆放总数了。
N = int(input())
a,b,c=list(map(int, input().split()))
cfx=[a,b,c]
mxcount = [N//a, N//b, N//c]
allres = []
def dfs(cur, n, st):
if cur == 3:
if n == 0:
allres.append(list(map(int, st.split(',')[1:])))
return
for i in range(0, mxcount[cur]+1):
num = n - cfx[cur]*i
if num>=0:
dfs(cur+1, num, st+','+str(i))
else:
return
return
# 求Akk
def getA(k):
res = 1
for i in range(1, k+1):
res *= i
return res
dfs(0, N, '')
sum = 0
for x,y,z in allres:
t = x+y+z
sum+= getA(t)//(getA(x)*getA(y)*getA(z))
print(sum)
发表于 2020-02-23 18:17:00
回复(0)
#include<iostream>
#include<cstdio>
#include<set>
#include<algorithm>
#include<cmath>
#include<vector>
#include<stack>
#include<cstring>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
const ll maxn = 2e5 + 10;
ll a,b,c, f[200];
ll n,k,ans;
ll v[200];
int main()
{
//freopen("input.c", "r", stdin);
cin>>n;
cin>>a>>b>>c;
if(a == b && b == c){
v[1] = a;
k = 1;
}
else if(a == b && b != c){
v[1] = a; v[2] = c;
k = 2;
}
else if(a != b && b == c){
v[1] = a; v[2] = b;
k = 2;
}
else{
v[1] = a; v[2] = b; v[3] = c;
k = 3;
}
f[0] = 1;
for(int i = 0; i <= n; i ++){
for(int j = 1; j <= k; j ++){
if(v[j] <= i) f[i] += f[i-v[j]];
}
}
cout<<f[n]<<endl;
return 0;
}
编辑于 2020-02-12 16:35:01
回复(0)
import math
height =int(input())
x,y,z =list(map(int,input().split()))
def comb_1(n,m): # 自定义求组合函数
return math.factorial(n)//(math.factorial(n-m)*math.factorial(m)) #阶乘函数math.factorial()
num =0
if height < x:
pass
else:
for i in range(100): #遍历求出需要的长宽高的次数
for j in range(100):
for k in range(100):
if i *x +j *y +k *z ==height:
num +=comb_1(i+j+k,i)*comb_1(j+k,j) #求组合结果
print(num)
发表于 2019-09-14 21:55:45
回复(0)
动态规划
#include <iostream>
#include<vector>using namespace std;
int main()
{
int target;
cin >> target;
vector<int> data;
int tmp;
while (cin >> tmp) {
data.push_back(tmp);
}
vector<int> dp(101, 0);
dp[0] = 1;
for (auto c : data) {
dp[c] = 1;
}
for (int i = data[0]+1; i <= 100; i++) {
for (auto c : data) {
if (i - c > 0) {
dp[i] += dp[i - c];
}
}
}
cout << dp[target];
}
发表于 2019-09-07 10:36:28
回复(1)
#include <iostream>
#include <algorithm>
using std::cout;
using std::cin;
using std::endl;
class Cuboid{
public:
Cuboid(size_t N,size_t l,size_t w,size_t h)
:_types(0),_totalH(N)
{
_arr[0] = l;
_arr[1] = w;
_arr[2] = h;
std::sort(_arr,_arr+3);
{
if(h == _totalH)
{
_types++;
return;
}
if(h > _totalH)
{
return;
}
for(int i =0;i<3;i++)
{
putCuboid(h+_arr[i]);
}
}
void showRes()
{
cout << _types << endl;
}
private:
size_t _arr[3];
size_t _types;
size_t _totalH;
};
int main()
{
size_t N,inLen,inWide,inHigh;
cin >> N >> inLen >> inWide >> inHigh;
Cuboid myCuboid(N,inLen,inWide,inHigh);
myCuboid.putCuboid(0);
myCuboid.showRes();
return 0;
}
#include <algorithm>
using std::cout;
using std::cin;
using std::endl;
class Cuboid{
public:
Cuboid(size_t N,size_t l,size_t w,size_t h)
:_types(0),_totalH(N)
{
_arr[0] = l;
_arr[1] = w;
_arr[2] = h;
std::sort(_arr,_arr+3);
}
//摆放长方体方式的遍历，使用深度优先的递归算法
void putCuboid(size_t h){
if(h == _totalH)
{
_types++;
return;
}
if(h > _totalH)
{
return;
}
for(int i =0;i<3;i++)
{
putCuboid(h+_arr[i]);
}
}
void showRes()
{
cout << _types << endl;
}
private:
size_t _arr[3];
size_t _types;
size_t _totalH;
};
int main()
{
size_t N,inLen,inWide,inHigh;
cin >> N >> inLen >> inWide >> inHigh;
Cuboid myCuboid(N,inLen,inWide,inHigh);
myCuboid.putCuboid(0);
myCuboid.showRes();
return 0;
}
发表于 2019-08-26 17:04:55
回复(0)
#include <iostream>
#include <cstdio>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
int opre_kinds=0;
void comb(vector<int>size,int sum,int cur){
// cout << cur <<endl;
for(int i=0;i<size.size();i++){
if(cur+size[i]==sum){
opre_kinds++;
return ;
}
else if(cur+size[i]>sum){
return ;
}
else
comb(size,sum,cur+size[i]);
}
}
int main(int argc, char const *argv[])
{
int N;
int x,y,z;
while (scanf("%d",&N)!=EOF)
{
opre_kinds=0;
scanf("%d %d %d",&x,&y,&z);
vector<int> size;
size.push_back(x);
if(y!=x)
size.push_back(y);
if(z!=x && z!=y)
size.push_back(z);
std::sort(size.begin(),size.end());
comb(size,N,0);
cout << opre_kinds <<endl;
}
return 0;
}
发表于 2019-08-24 18:30:23
回复(1)
问题信息
通过挑战的用户
-
2022-11-05 13:45:10 -
2022-10-28 18:54:00
-
2022-10-28 12:12:04
-
2022-10-27 18:31:25 -
2022-10-27 15:29:02
相关试题
-
评论(1)
-
评论(6) 来自深信服2019春招技术岗...
-
评论(82) 来自深信服2019春招技术岗...
-
评论(38) 来自深信服2019春招技术岗...
-
评论(18) 来自深信服2019春招技术岗...
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
