UPC-Match Matching（完全背包dp+字符串）

但因热爱 愿迎万难。

问题 M: Match Matching

时间限制: 1 Sec 内存限制: 128 MB

[提交] [状态]

题目描述

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.

样例输入 Copy

20 4

3 7 8 4

样例输出 Copy

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.

题意： 给定n根火柴，m个数，每个数代表能够使用的火柴的值，比如2表示能够使用1这根火柴，问用n根这m个数代表的火柴能够拼成的数字最大是多少。（有点混乱）

思路：

这是个很典型的 完全背包叭，再结合贪心的思想，先比较长度，相同长度再比较大小。

思路不难想，重要的是如何实现。

下面是开字符串数组的做法，用到了一个函数to_string将数字转化成字符串，再利用字符串可以直接相加的原则，直接进行状态转移。

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+7;
int a[maxn],b[maxn];
int n,m;
string dp[maxn];
int c[10] = {0, 2, 5, 5, 4, 5, 6, 3, 7, 6};
int main(){
   scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++) scanf("%d",&a[i]);
    //  dp[0]="";//初始化（可忽略）
    ///cout<<dp[0]<<endl;
    for(int i=1;i<=n;i++){
            //dp[i]="";（可忽略）
            for(int j=0;j<m;j++){
                if((i-c[a[j]])<0||((i-c[a[j]])!=0 &&dp[i-c[a[j]]]=="")) continue;//此状态无法由其他状态转移过来
                   /// dp[i]=max(dp[i],dp[i-c[a[j]]]+to_string(a[j]));
                if(dp[i].size()<dp[i-c[a[j]]].size()+1)//先选择最长的
                    dp[i]=dp[i-c[a[j]]]+to_string(a[j]);
                else if(dp[i].size()==dp[i-c[a[j]]].size()+1)//相同长度再选择最大的
                    dp[i]=max(dp[i],dp[i-c[a[j]]]+to_string(a[j]));
            }
        }
        cout<<dp[n]<<endl;
    return 0;
}

好敷衍的题解

您也可以去看另外的做法传送门

补一波作业去

3月Flag：改掉拖延！