牛牛给了小度n根火柴和m种数字(m只能是1到9),小度只能摆这m种数字,小度想知道能摆出来最大的数的多少。
如图所示: 摆数字1,2,3,4,5,6,7,8,9 分别需要花费 2,5,5,4,5,6,3,7,6根火柴。
第一行两个数n,m。
第二行m个数,表示小度可以摆放的数。
一行表示答案。
20 4 3 7 8 4
777773
火柴得使用完
#include<bits/stdc++.h> int dig_weight[] = {2, 5, 5, 4, 5, 6, 3, 7, 6}; using namespace std; int main() { int capacity, n_item; cin >> capacity >> n_item; vector<int> weight(9, 0x3ffffff); for (int i = 0; i < n_item; ++i) { int dig; cin >> dig; weight[dig - 1] = dig_weight[dig - 1]; } vector<int> dp(capacity + 1,-0x3ffffff); dp[0] = 0; for (int i = 1; i <= 9; ++i) { for (int j = weight[i - 1]; j <= capacity; ++j) { dp[j] = max(dp[j], dp[j - weight[i - 1]] + 1); } } string ans; for (int i = 9, j = capacity; i >= 1; --i) { for (int cost = weight[i - 1]; j >= cost && dp[j] == dp[j - cost] + 1; j -= cost) { ans += (i + '0'); } } cout << ans; }
import java.util.*; import java.io.*; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { private static int[] cnt = new int[]{2,5,5,4,5,6,3,7,6}; private static int maxNum = 0; public static void main(String[] args) throws IOException{ BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); String[] s = in.readLine().split(" "); int n = Integer.parseInt(s[0]), m = Integer.parseInt(s[1]); s = in.readLine().split(" "); Integer[] can = new Integer[m]; for(int i = 0; i < m; i++){ can[i] = Integer.parseInt(s[i]); } Arrays.sort(can); int[] dp = new int[n+1]; Arrays.fill(dp, -0x3ffffff); dp[0] = 0; for(int i = 0; i < m; i++){ for(int j = cnt[can[i]-1]; j <= n; j++){ dp[j] = Math.max(dp[j], dp[j-cnt[can[i]-1]]+1); } } StringBuffer sb = new StringBuffer(); for(int i = m - 1, j = n; i >= 0; i--){ for(int cost = cnt[can[i]-1]; j >= cost && (dp[j] == dp[j-cost]+1); j -= cost){ sb.append(can[i]); } } System.out.println(sb); } }
#include <cstdio> #include <iostream> #include <map> #include <algorithm> #include <vector> #include <string> using namespace std; // 每个数字需要消耗的火柴数 constexpr int stick_cnt[10] = {0, 2, 5, 5, 4, 5, 6, 3, 7, 6}; // 对剩余的火柴可能摆放的数字情况 vector<string> possible_stuff; // 输入中 可用的数字,以及对应的火柴消耗 vector<int> number, cnt; // 递归判断剩余火柴可能的摆放情况 void find_fit_stuff(int rest, const string& s) { if (rest < 0) return; if (rest == 0) { possible_stuff.emplace_back(s); } for (int i = 0; i < cnt.size(); i++) { // try every number find_fit_stuff(rest - cnt[i], s + to_string(number[i])); } } int main() { int n, m; scanf("%d%d", &n, &m); map<int, int> mp; for (int i = 0; i < m; i++) { int x; scanf("%d", &x); // 如果当前这种火柴数消耗还没有出现过,直接加入; // 否则挑选数值更大的记录 if (mp.find(stick_cnt[x]) == mp.end()) { mp.emplace(stick_cnt[x], x); } else { if (x > mp[stick_cnt[x]]) { mp[stick_cnt[x]] = x; } } } for (auto it: mp) { cnt.emplace_back(it.first); number.emplace_back(it.second); } // 假设先用消耗最少的摆放 int min_number_cnt = n / cnt[0], rest = n % cnt[0]; // 如果根本没有剩余,那么直接输出就可以了 if (!rest) { cout << string(min_number_cnt, number[0] + '0') << endl; return 0; } // 持续减少最小火柴消耗的数字数量, // 直到能够找到一种数字排列使得所有火柴都能用完 for (int i = 1; i < min_number_cnt && possible_stuff.size() == 0; i++) { find_fit_stuff(rest + i * cnt[0], ""); min_number_cnt--; } // 优先挑选最长的,然后再考虑字典序 sort(possible_stuff.begin(), possible_stuff.end(), [](const string& self, const string& other) -> bool { return self.size() == other.size() ? self > other : self.size() > other.size(); }); // 这里已经知道最终使用哪两个字符串进行拼凑,选一个起始位最大的作为开头 string final_prefix(min_number_cnt, number[0] + '0'); cout << ((final_prefix[0] > possible_stuff[0][0]) ? final_prefix + possible_stuff[0] : possible_stuff[0] + final_prefix) << endl; return 0; }
import sys l = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6} a = list(map(int, input().split())) b = list(map(int, input().split())) c = [] x = {} for i in range(a[1]): c.append(l[b[i]]) x[b[i]] = l[b[i]] x = sorted(x.items(), key=lambda x: x[1]) d = [0 * i for i in range(a[0]+1)] s = ["" for i in range(a[0]+1)] for j in range(a[0]+1): for i in range(len(x)): if j >= x[i][1]: d[j] = max(d[j], 1 + d[j - x[i][1]]) if (s[j - x[i][1]] != ''&nbs***bsp; j - x[i][1] == 0): if s[j - x[i][1]] == '': if len(s[j]) < len(str(x[i][0])): s[j] = str(x[i][0]) elif len(s[j]) == len(str(x[i][0])): if int(s[j]) < int(str(x[i][0])): s[j] = str(x[i][0]) else: if len(s[j]) < len(str(x[i][0]) + s[j - x[i][1]]): s[j] = str(x[i][0]) + s[j - x[i][1]] elif len(s[j]) == len(str(x[i][0]) + s[j - x[i][1]]): if int(s[j]) < int(str(x[i][0]) + s[j - x[i][1]]): s[j] = str(x[i][0]) + s[j - x[i][1]] print(s[-1])
#include <bits/stdc++.h> using namespace std; static int weight[10] = {0,2,5,5,4,5,6,3,7,6}; string max_str(const string& str1, const string& str2) { int n1 = str1.size(); int n2 = str2.size(); if(n1 > n2) return str1; else if(n1 < n2) return str2; if(str1.compare(str2) < 0) return str2; return str1; } unordered_map<int,string> dp; int main() { int capacity, m; cin >> capacity >> m; vector<int> nums(m , 0); for(int i = 0;i < m;i++) cin >> nums[i]; for(int i = 1;i <= capacity;i++) dp[i] = ""; for(int j = 1;j <= capacity;j++) for(int i = 0;i < m;i++) if(j-weight[nums[i]] >= 0) // j == weight[nums[i]] 进行初始化 if(dp[j-weight[nums[i]]] != "" || j == weight[nums[i]]) dp[j] = max_str(dp[j], to_string(nums[i]) + dp[j - weight[nums[i]]]); cout << dp[capacity] << endl; return 0; }
#include <iostream> #include <vector> using namespace std; const vector<int> fate = { 0, 2, 5, 5, 4, 5, 6, 3, 7, 6 }; int comp(string s1, string s2) { if (s1.size() > s2.size()) { return 1; } else if (s1.size() < s2.size()) { return -1; } else { return s1.compare(s2);; } } int main() { int n, m; cin >> n >> m; vector<int> set(m); for (int i = 0; i < m; ++i) cin >> set[i]; vector<string> dp(n + 1, ""); for (int i = 2; i < n + 1; ++i) { for (int j = 0; j < m; ++j) { if (i >= fate[set[j]]) { if (dp[i - fate[set[j]]] != "" || i == fate[set[j]]) { string ns = dp[i - fate[set[j]]] + (char)(set[j] + '0'); int ret = comp(dp[i], ns); if (ret < 0) dp[i] = ns; } } } } cout << dp[n] << endl; return 0; }
#include <iostream> #include <vector> #include <algorithm> #include <string> #include <unordered_map> using namespace std; static unordered_map<int, int> costs = { {1, 2}, {2, 5}, {3, 5}, {4, 4}, {5, 5}, {6, 6}, {7, 3}, {8, 7}, {9, 6}, }; void FindNumber(const vector<int>& A, int n, int i, string& s, vector<string>& res) { // return when we find the first match if (!res.empty() || n == 0) { if (n == 0) res.push_back(s); return; } for (int j = i; j < A.size(); ++j) { int c = costs[A[j]]; if (c <= n) { char d = (char)(A[j] + '0'); s.push_back(d); FindNumber(A, n - c, j, s, res); s.pop_back(); } } } void PrintMaxNumber(int n, vector<int>& A) { // sort A by cost in the ascending order // (large number first if cost equals) sort(A.begin(), A.end(), [](int l, int r) { return costs[l] != costs[r] ? costs[l] < costs[r] : r < l; }); string cur; vector<string> res; FindNumber(A, n, 0, cur, res); if (!res.empty()) { // rearrange the order of characters such that the large digit // comes first sort(res[0].begin(), res[0].end(), greater<int>()); cout << res[0] << endl; } } int main() { int m, n; cin >> n >> m; vector<int> A(m); for (int i = 0; i < m; ++i) { cin >> A[i]; } PrintMaxNumber(n, A); }
#include <iostream> #include <vector> #include <set> #include <map> #include <string> #include <algorithm> using namespace std; set<string> ret; vector<int> nn, ch; void f(int num, string s) { if (num < 0) { return; } if (num == 0) { ret.insert(s); return; } for (int i = 0; i <nn.size(); i++) { f(num - nn[i], s + to_string(ch[i])); } } bool cmp(string a, string b) { if (a.size() == b.size()) { return a < b; } else return a.size() < b.size(); } bool chcmp(char a, char b) { return a > b; } int main() { int n, m, a; cin >> n >> m; int num[10] = { 0,2,5,5,4,5,6,3,7,6 }; vector<int> ve; map<int, int> ma; for (int i = 0; i < m; i++) { cin >> a; if (ma.find(num[a]) == ma.end()) { ma[num[a]] = a; } else { if (a > ma[num[a]]) { ma[num[a]] = a; } } } for (auto it : ma) { nn.push_back(it.first); ch.push_back(it.second); } ma.clear(); int d = n % nn[0], cnt = n / nn[0]; while (ret.size() == 0) { string s; d = d + nn[0]; cnt--; f(d, s);//找出d根火柴在限定可能性的情况下是否能刚好摆出数字。 } vector<string> ss(ret.size()); int i = 0; for (auto it : ret) { ss[i++] = it; } sort(ss.begin(), ss.end(), cmp); string s = ss[ret.size() - 1];//找出ss中长度最长、数字最大的组合。 while (cnt--) { s = s + to_string(ch[0]); } sort(s.begin(), s.end(),chcmp);//对数字进行排序 cout << s << endl; return 0; }