华为OD机考双机位B卷 - 组装新的数组（Java Python JS C/C++ GO ）-程序员充电站

题目描述

给你一个整数M和数组N，N中的元素为连续整数，要求根据N中的元素组装成新的数组R，组装规则：

R中元素总和加起来等于M
R中的元素可以从N中重复选取
R中的元素最多只能有1个不在N中，且比N中的数字都要小（不能为负数）

输入描述

第一行输入是连续数组N，采用空格分隔
第二行输入数字M

备注

1 ≤ M ≤ 30
1 ≤ N.length ≤ 1000

输出描述

输出的是组装办法数量，int类型

示例1

输入

2 5

输出

说明

只有1种组装办法，就是[2,2,1]

示例2

输入

2 3 5

输出

说明

一共两种组装办法，分别是[2,2,1]，[2,3]

解题思路

Java

importjava.util.*;publicclassMain{publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);Stringline=sc.nextLine();List<Integer>arr=newArrayList<>();String[]nums=line.split(" ");for(Stringnum:nums){arr.add(Integer.parseInt(num));}intm=sc.nextInt();// 获取数组中的最小值intmin_num=Collections.min(arr);// 动态规划int[]dp=newint[m+1];dp[0]=1;for(intnum:arr){for(inti=num;i<=m;i++){dp[i]+=dp[i-num];}}intcount=dp[m];for(inti=1;i<min_num;i++){count+=dp[m-i];}System.out.println(count);}}

Python

defmain():line=input().strip()arr=list(map(int,line.split()))m=int(input())# 获取数组中的最小值min_num=min(arr)# 动态规划dp=[0]*(m+1)dp[0]=1fornuminarr:foriinrange(num,m+1):dp[i]+=dp[i-num]count=dp[m]foriinrange(1,min_num):count+=dp[m-i]print(count)if__name__=="__main__":main()

JavaScript

constreadline=require('readline');constrl=readline.createInterface({input:process.stdin,output:process.stdout});rl.on('line',(line)=>{constarr=line.split(' ').map(Number);rl.on('line',(mInput)=>{constm=parseInt(mInput,10);// 获取数组中的最小值constminNum=Math.min(...arr);// 动态规划constdp=newArray(m+1).fill(0);dp[0]=1;for(constnumofarr){for(leti=num;i<=m;i++){dp[i]+=dp[i-num];}}letcount=dp[m];for(leti=1;i<minNum;i++){count+=dp[m-i];}console.log(count);rl.close();});});

C++

#include<iostream>#include<vector>#include<sstream>#include<algorithm>using namespace std;intmain(){string line;getline(cin,line);vector<int>arr;istringstreamiss(line);intnum;while(iss>>num){arr.push_back(num);}intm;cin>>m;// 获取数组中的最小值intmin_num=*min_element(arr.begin(),arr.end());// 动态规划vector<int>dp(m+1,0);dp[0]=1;for(intnum:arr){for(inti=num;i<=m;i++){dp[i]+=dp[i-num];}}intcount=dp[m];for(inti=1;i<min_num;i++){count+=dp[m-i];}cout<<count<<endl;return0;}

Go

package main import ( "bufio" "fmt" "math" "os" "strconv" "strings" ) func main() { // 创建 scanner 读取输入 scanner := bufio.NewScanner(os.Stdin) // 1. 读取第一行 if !scanner.Scan() { return } line := scanner.Text() // 2. 解析数组 var arr []int minNum := math.MaxInt32 // Fields 会自动处理多个连续空格，并去除首尾空格 strNums := strings.Fields(line) for _, strNum := range strNums { num, err := strconv.Atoi(strNum) if err == nil { arr = append(arr, num) // 寻找最小值 if num < minNum { minNum = num } } } // 3. 读取 m // 继续扫描下一行或下一个 token if !scanner.Scan() { return } mStr := scanner.Text() // 如果 m 和数组在同一行但被换行符隔开，或者 m 独占一行， m, _ := strconv.Atoi(strings.TrimSpace(mStr)) // 4. 动态规划 dp := make([]int, m+1) dp[0] = 1 for _, num := range arr { for i := num; i <= m; i++ { dp[i] += dp[i-num] } } // 5. 计算结果 count := dp[m] for i := 1; i < minNum; i++ { if m-i >= 0 { count += dp[m-i] } } fmt.Println(count) }

C语言

#include<stdio.h>#include<stdlib.h>#include<string.h>#include<limits.h>#defineMAX_LINE_LENGTH100000intmain(){// 1. 读取第一行输入 (数组)charline[MAX_LINE_LENGTH];if(fgets(line,sizeof(line),stdin)==NULL){return0;}// 2. 解析整数存入动态数组 (这里为了简单使用定长数组，可根据需要改为 malloc)int*arr=NULL;intarr_size=0;intarr_capacity=100;arr=(int*)malloc(arr_capacity*sizeof(int));intmin_num=INT_MAX;// 使用 strtok 分割空格char*token=strtok(line," \r\n");// 同时处理回车换行符while(token!=NULL){if(arr_size>=arr_capacity){arr_capacity*=2;arr=(int*)realloc(arr,arr_capacity*sizeof(int));}intnum=atoi(token);arr[arr_size++]=num;// 寻找最小值if(num<min_num){min_num=num;}token=strtok(NULL," \r\n");}// 3. 读取 mintm;scanf("%d",&m);// 4. 动态规划// 使用 calloc 初始化为 0int*dp=(int*)calloc(m+1,sizeof(int));dp[0]=1;for(intk=0;k<arr_size;k++){intnum=arr[k];for(inti=num;i<=m;i++){dp[i]+=dp[i-num];}}// 5. 计算结果longlongcount=dp[m];// 使用 long long 防止累加溢出，尽管 Java 原版用的 intfor(inti=1;i<min_num;i++){if(m-i>=0){count+=dp[m-i];}}printf("%lld\n",count);// 释放内存free(arr);free(dp);return0;}