Luogu P2549 计算器写作文 题解

一、转化题意

给定 $n$ 个大数，拼接其中一些，位数不超过 $d$，可以加小数点（不算位数），求位数的最大值

显然如果不是全都有前导 0，不需要加小数点

二、为什么是 $01$ 背包？

在 $N$ 个字符串取出若干个放在长度为 $D$ 的“背包”里，每个数字的长度为 $l_1,l_2...l_n$，与之相对应的价值为 $d_1,d_2...d_n$。

显然是符合定义的

于是可以写出方程 $dp_j=\max\{dp_j,dp_{j-L_i}+d_i\}$

三、细节处理

可以注意到 $dp$ 和 $d$ 数组均是字符串，不妨将 $+$ 定义为字符串的拼接，为保证无后效性，显然可以将 $d$ 数组排序

3k 说要按字典序排序，但是这似乎不对

这里需要分类讨论：

1. 存在不含前导 0 的字符串

这种情况很简单，$cmp$ 函数直接写 $a+b>b+a$ 就行，注意重载 $>$ 运算符

注意它与字典序排序是不同的，例如字典序排序中 $"1">"12"$，但是实际上 $112<121$，并不是最优解

2. 不存在不含前导 0 的字符串

这种情况就是基本的字典序排序

然后就完了，输出 $dp[m]$ 即可

四、代码实现

我自己是用结构体封装重载运算符的，看上去比较舒服，至少 dp 式子拿来就用

#include <bits/stdc++.h>
#define inl inline
#define rep(i,a,b) for(int i=(a),i##end=(b);i<=i##end;++i)
#define pre(i,a,b) for(int i=(a),i##end=(b);i>=i##end;--i)
using namespace std;
map<char,int>mp;bool pd;//pd 表示是否全部含有前导 0,1 表示存在不含前导 0 的
struct Node{
    int d[210],l;//d 数组就是上文的 d 数组，l 表示 d 数组的长度
    inl Node operator+(const Node b)const{
        Node c;
        rep(i,1,l)c.d[i]=d[i];rep(i,1,b.l)c.d[i+l]=b.d[i];
        c.l=l+b.l;
        return c;
    }//+ 重载为字符串拼接
    inl bool operator>(const Node b)const{
        if(pd){
            if(l!=b.l)return l>b.l;
            rep(i,1,l)if(d[i]!=b.d[i])return d[i]>b.d[i];
            return 0;
        }
        int len=min(l,b.l);
        rep(i,1,len)if(d[i]!=b.d[i])return d[i]>b.d[i];
        return l>b.l;
    }//重载了 > 号
}a[10010],dp[210];
inl Node max(Node a,Node b){return a>b?a:b;}//重载 max，因为 C++ 中的 max 是基于 < 号的，也是为了卡卡常
inl bool cmp(Node a,Node b){
    if(pd)return (a+b)>(b+a);//1. 存在不含前导 0 的字符串
    int len=min(a.l,b.l);
    rep(i,1,len)if(a.d[i]!=b.d[i])return a.d[i]>b.d[i];
    return a.l>b.l;//2. 不存在不含前导 0 的字符串
}
signed main(void){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    mp['O']=0,mp['D']=0,mp['G']=9,mp['B']=8,mp['L']=7,mp['q']=6,mp['S']=5,mp['h']=4,mp['E']=3,mp['Z']=2,mp['I']=1;//由题中的图可以得到这样一张表
    int m,n;cin>>m>>n;
    rep(i,1,n){
        string s;cin>>s;
        reverse(s.begin(),s.end());
        a[i].l=s.size();
        rep(j,0,a[i].l-1)a[i].d[j+1]=mp[s[j]];//字母字符串倒序再映射为数字字符串
        if(a[i].d[1]>0)pd=1;
    }
    sort(a+1,a+n+1,cmp);
    rep(i,1,n)pre(j,m,a[i].l)dp[j]=max(dp[j],dp[j-a[i].l]+a[i]);//可爱的 dp
    cout<<dp[m].d[1];
    if(!pd)cout<<'.';
    rep(i,2,dp[m].l)cout<<dp[m].d[i];
}