火柴棍能组成的最大数字

旧城等待， 2023-07-15 02:46 11阅读 0赞

## 火柴棍能组成的最大数字 ##

#### 2020春招百度笔试题 ####

题目：

> **输入火柴棍根数n，能选取的数字个数m，以及能选取的数字列表  
> 输入案例（原题案例我忘了，瞎写的）  
> 20 4  
> 5 6 7 8  
> 输出能组成的最大整数值**

题解：使用动态规划，[代码github链接][github] ，如有错误还望指出，新手上路，请多关照

#include <cstdio>
    #include <cmath>
    #include <vector>
    
    using namespace std;
    int number[10] = {
         0,1,2,3,4,5,6,7,8,9 };
    int expend[10] = {
         0,2,5,5,4,5,6,3,7,6 };
    int main() {
        
    	int n, m;
    	scanf("%d", &n);
    	scanf("%d", &m);
    	vector<bool> canuse(10, false);
    	vector<int> dp(n+1,0);
    	for (int i = 0; i<m; i++) {
        
    		int temp;
    		scanf("%d", &temp);
    		canuse[temp] = true;
    	}
    	dp[0]=0;
    	for(int i=1;i<=n;i++){
        
    		int choice=0;
    		int maxvalue=0;
    		for(int j=1;j<=9;j++){
        
    			if(canuse[j]) {
        
    				if(i-expend[j]<0) continue;
    				if(dp[i-expend[j]]==-1) continue;
    				if(dp[i-expend[j]]>=maxvalue){
        
    					choice=j;
    					maxvalue=dp[i-expend[j]];
    				}
    			}
    		}
    		if(choice==0) dp[i]=-1;
    		else{
        
    			dp[i]=maxvalue*10+choice;
    		}
    		//printf("%d\n",dp[i]);
    	}
    	printf("%d",dp[n]);
    	return 0;
    }

**2020年3月14日**

[github]: https://github.com/zmhhaha/interview_code/blob/master/%E7%81%AB%E6%9F%B4%E8%83%BD%E6%8B%BC%E5%87%BA%E7%9A%84%E6%9C%80%E5%A4%A7%E6%95%B0%E5%AD%97.cpp

发表评论取消回复

表情：

评论列表（有 0 条评论，11人围观）

还没有评论，来说两句吧...

相关阅读

相关火柴棍能组成的最大数字

火柴棍能组成的最大数字 2020春招百度笔试题题目： > 输入火柴棍根数n，能选取的数字个数m，以及能选取的数字列表 > 输入案例（原题案例我忘了，瞎写的）

旧城等待，/ 2023年07月15日 02:46/ 0 赞/ 12 阅读

相关 leetcode 949 给定数字能组成的最大时间

给定一个由 4 位数字组成的数组，返回可以设置的符合 24 小时制的最大时间。最小的 24 小时制时间是 00:00，而最大的是 23:59。从 00:00 （午夜）开始算

深藏阁楼爱情的钟/ 2023年06月29日 02:53/ 0 赞/ 21 阅读

相关字符串中最大的数字

错误代码 include<stdio.h> define N 100 int main(void) { char str

灰太狼/ 2022年12月17日 08:38/ 0 赞/ 180 阅读

相关 LeetCode:1323. Maximum 69 Number6 和 9 组成的最大数字(C语言)

题目描述：给你一个仅由数字 6 和 9 组成的正整数 num。你最多只能翻转一位数字，将 6 变成 9，或者把 9 变成 6 。请返回你可以得到的最大数字。示

朱雀/ 2022年11月25日 13:13/ 0 赞/ 17 阅读

相关多个数组成最大数字

题目信息小组中有多个人，每个人手中有一个卡片，卡片上是6位内的正整数，将卡片连接起来可以组成多个数字，计算可以组成的最大数字。输入描述逗号“,” 分割的多个

港控/mmm°/ 2022年11月05日 09:56/ 0 赞/ 108 阅读

相关 SVG新年火柴棍动画

正在学习SVG，弄个2014年的火柴棍动画，大家先看[效果][Link 1]。 ![SouthEast][] 这个主要是用到了SVG的内置动画，大家可以参考msdn上

旧城等待，/ 2022年08月24日 14:25/ 0 赞/ 244 阅读

相关啊哈！算法—火柴棍等式

现手中有m(m<=24)个火柴棍，希望拼出A+B=C等式。等式中的A、B、C均为火柴棍拼出来的整数（若该数非0，则最高位不能为0）。注意： 1、加号与等号各自需要2根火

小灰灰/ 2022年08月21日 12:47/ 0 赞/ 227 阅读

相关火柴棍

//火柴棍：输入整数n，输出能拼成的不同等式的数目 include<iostream> using namespace std; int ma

「爱情、让人受尽委屈。」/ 2022年06月16日 08:08/ 0 赞/ 196 阅读

相关算法火柴棍问题

题目：现在有n根火柴棍，拼出A+B=C的等式。注意：加号和等号各自需要两根火柴棍，A不等于B,则A+B=C与B+A=C是为不同的等式，所有火柴棍必须都用上。这个题刚看到

太过爱你忘了你带给我的痛/ 2022年05月30日 05:07/ 0 赞/ 240 阅读

相关 day13(力扣)给定数字能组成的最大时间(python描述)

题目描述：给定一个由 4 位数字组成的数组，返回可以设置的符合 24 小时制的最大时间。最小的 24 小时制时间是 00:00，而最大的是 23:59。从 00:00 （午夜）

- 日理万妓/ 2021年11月09日 05:56/ 0 赞/ 310 阅读