背包,f[i]表示计算器位数为i时,可获得的最大分值.
本题与01背包不同的地方在于,物品的摆放顺序对答案是有影响的,例如两个字符串a,b,那么就会出现a+b和b+a两种情况(注意这是字符串),
而这又违背了DP的无后效性
因为我们先转移的i物品一定是在后转移的i+1物品的前面，就是说串i+1一定是加在了串i的后面某个位置（如果能加的话）。
所以显然也有可能是i+1这个串出现在i这个串的前面，所以显然现在是有后效性的.
那怎么办呢?排序!(请看代码cmp函数)
还有就是因为本题的f不是int,所以重新定义了一下max.
1 #include<iostream> 2 #include<cstdio> 3 #include<map> 4 #include<algorithm> 5 6 using namespace std; 7 8 int d,n,ppp; 9 string g[10001],f[201]; 10 map<char,int> a; 11 12 inline void make_map() { 13 a[‘O‘] = a[‘D‘] = 0; 14 a[‘G‘] = 9; 15 a[‘B‘] = 8; 16 a[‘L‘] = 7; 17 a[‘q‘] = 6; 18 a[‘S‘] = 5; 19 a[‘h‘] = 4; 20 a[‘E‘] = 3; 21 a[‘Z‘] = 2; 22 a[‘I‘] = 1; 23 } 24 25 inline bool cmp(string l,string b) { 26 string x = l + b; 27 string y = b + l; 28 return x < y; 29 } 30 31 inline string _max(string l,string b) { 32 int u = l.length(); 33 int o = b.length(); 34 if(u == 0) return b; 35 if(o == 0) return l; 36 if(l[0] != ‘0‘ && b[0] != ‘0‘) 37 if(u > o) return l; 38 else if(u < o) return b; 39 if(l < b) return b; 40 return l; 41 } 42 43 int main() { 44 scanf("%d%d",&d,&n); 45 make_map(); 46 for(int i = 1;i <= n; i++) { 47 string p; 48 cin >> p; 49 for(int j = p.length();j >= 1; j--) 50 g[i] += (a[p[j-1]] + ‘0‘); 51 } 52 sort(g+1,g+n+1,cmp); 53 for(int i = n;i >= 1; i--) 54 for(int j = d;j >= g[i].length(); j--) 55 f[j] = _max(f[j],f[j-g[i].length()] + g[i]); 56 if(f[d][0] == ‘0‘){ 57 printf("0."); 58 ppp++; 59 } 60 for(int i = ppp;i < f[d].length(); i++) 61 cout << f[d][i]; 62 return 0; 63 }
原文：https://www.cnblogs.com/lipeiyi520/p/12339786.html