寒假集训DAY2 T4

lyrzs · 2023-01-10 16:18:39 · 个人记录

题干： 小信有n根木棍，他想拼出只包含给定的m种数字中的至少一种数字的数字串。

已知数字1,2,3,4,5,6,7,8,9分别需要2,5,5,4,5,6,3,7,6根火柴。要求n根木棍全部都用完且拼成的数字最大，输出这个数字。保证答案存在。

题目概括： 取和刚好为n的数组成火柴数，要求组成的“火柴数”最大

思路：

打开比赛看到D题时一眼记忆化搜索，但是写到一半突然发现处理字符串带入递归好像没有什么简便一些的方法（没想出来），就开始思考动态规划的做法。分析题目，每种给定的数字都可以无限制的取，这是完全背包的特性，其中每种数字消耗的火柴数就是代价（空间），而给定的n就是背包容量，以此转换，这题就变成了一道背包题，不过有一点要注意，取一个数字，获得的价值就是在数位上增添这个数，考虑数据范围可以得知int，long long是存储不下的，于是就有了字符串拼接的方法

算法：

传统的完全背包问题，计算价值时用手写的比较函数比较两个字符串表示的数的大小，最后的答案就是f[n]

AC代码：

#include<bits/stdc++.h>
using namespace std;
int n,m;
string f[100005];
string a[10005];
int d[100]={0,2,5,5,4,5,6,3,7,6};
bool check(string a,string b)
{
    if(a.size()>b.size())
        return true;
    if(a.size()<b.size())
        return false;
    for(int i=0;i<a.size();i++)
    {
        if(a[i]>b[i])
            return true;
        if(a[i]<b[i])
            return false;
     }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++)
        cin>>a[i];
    sort(a+1,a+m+1,check);
    for(int i=1;i<=m;i++)
    {
        int t=a[i][0]-'0';
        for(int j=d[t];j<=n;j++)
        {
            if(f[j-d[t]]!=""||j==d[t])
                if(!check(f[j],f[j-d[t]]+a[i]))
                    f[j]=f[j-d[t]]+a[i];
        }
     }
     cout<<f[n];
     return 0;
}