題目描述

Find the largest integer that can be formed with exactly N matchsticks, under the following conditions:
Every digit in the integer must be one of the digits A1,A2,...,AM(1≤Ai≤9).
The number of matchsticks used to form digits 1,2,3,4,5,6,7,8,9 should be 2,5,5,4,5,6
,3,7,6, respectively.
Constraints
·All values in input are integers.
·2≤N≤104
·1≤M≤9
·1≤Ai≤9
·Ai are all different.
·There exists an integer that can be formed by exactly N matchsticks under the conditions.

?

輸入

Input is given from Standard Input in the following format:

N M
A1 A2 ... AM

輸出

Print the largest integer that can be formed with exactly N matchsticks under the conditions in the problem statement.

?

樣例輸入

20 4 3 7 8 4

樣例輸出

777773

提示

The integer 777773 can be formed with 3+3+3+3+3+5=20 matchsticks, and this is the largest integer that can be formed by 20 matchsticks under the conditions.

---

題目大意：規定用火柴擺數字的樣子，從 1 ~ 9 所需要的火柴分別為2,5,5,4,5,6,3,7,6，現在給出 m 個不同的且小于十的數字，問恰好用完 n 根火柴，使得擺出的數字最大，且該數字必須使用提供的 m 個數字，問最大可以拼出的數字能有多大

題目分析：一開始感覺是先貪心后暴力，但看到需要恰好用掉 n 個火柴感覺有點蹊蹺，加上有 m 個數字的限制，使得貪心并不是如此簡單，后來發現 n 比較小，且必須要恰好用完 n ，使得結果最大，那不就是一個最優性問題，用dp來解決，恰好用完讓我想到了完全背包，這樣一來只要重載一下MAX函數，用字符串作為dp數組，花費為每個數字所需要的火柴數，價值為每個數字本身，轉移一遍就好了，注意初始化

代碼：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e5+100;int a[N];string dp[N];string val="0123456789";int cost[10]={0,2,5,5,4,5,6,3,7,6};string MAX(string a,string b) {if(a.size()>b.size())return a;if(a.size()<b.size())return b;return a>b?a:b; }int main() { #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif // ios::sync_with_stdio(false);int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=m;i++)scanf("%d",a+i);for(int i=0;i<=n;i++)dp[i]="-";dp[0]="";for(int i=0;i<=n;i++){if(dp[i]=="-")continue;for(int j=1;j<=m;j++)if(i+cost[a[j]]<=n)dp[i+cost[a[j]]]=MAX(dp[i+cost[a[j]]],dp[i]+val[a[j]]);}cout<<dp[n]<<endl;return 0; }

?

總結

以上是生活随笔為你收集整理的中石油训练赛 - Match Matching(完全背包)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。