luogu p2549

字符串01背包

#include <bits/stdc++.h>
using namespace std;
unordered_map<char,int> m = {{'D',0},{'O',0},{'G',9},{'B',8},{'L',7},{'q',6},{'S',5},{'h',4},{'E',3},{'Z',2},{'I',1}};
int D;
int n;
char ch[35];
const int MAXD = 210;
vector<string> v;
string dp[MAXD];

string maxs(string a,string b) 
{
    int na=a.size(),nb=b.size();
    if (na==0)//特殊情况 
    return b;
    if (nb==0)
    return a;
    if (a[0]!='0'&&b[0]!='0')
    {
        if (na!=nb)//先判位数 
        return na>nb?a:b;
        return a>b?a:b;
    }
    return a>b?a:b;
}

int main(){
    cin>>D;
    cin>>n;
    for(int i =1;i<=n;i++){
        scanf("%s",ch);
        string s = "";
        for(int i =strlen(ch)-1;i>=0;i--){
            s += to_string(m[ch[i]]);
        }
        v.push_back(s);
    }
    sort(v.begin(),v.end(),[](string a,string b){
        return a+b>b+a;
    }  );


    dp[0] = "";
    for(int i =0;i<v.size();i++){
        int sz = v[i].size();
        for(int j = D;j>=sz;j--){
            dp[j] = maxs(dp[j],dp[j-sz] + v[i]);
        }
    }
    if(dp[D][0]!='0')
        cout<<dp[D]<<endl;
    else{
        cout<<"0."; 
        for (int i=1;i<dp[D].size();i++)
            cout<<dp[D][i];
    }

    return 0;
}