一起来交流编程吧【CSDN app】：
http://qm.qq.com/cgi-bin/qm/qr?_wv=1027&k=x9pL9ccIHGKNLE0CWviAqQ_q6HzxomLW&authKey=VslKe623ptw8VRepda%2Bh0Ttr8Ruz8v%2FBW5HpVzyTWU7ECwpHIZpULMj6qIHYZBVb&noverify=0&gro
计算器写作文
题目描述
众所周知，计算器可以拿来干很多它本不应该干的事情，比如弹琴。
小A发现了一个计算器的隐藏功能——写英语作文。
他在计算器上按一些数字，这些然后旋转 180 度就是作文。
每个数字对应一两个字母
小A准备了一个单词表，选择其中的一些单词，按照一个顺序组成作文。这个作文是可以用计算器按出来的。比如单词表给“ODD”、“EGG”，作文写成“ODDEGG”的话，那么要在计算器上按出“993000”，这篇作文的得分就是993000。
单词表的单词不能重复使用。如果单词表出现了多个一样的单词，每个单词最多都可以各使用一次。单词不可以被截断。
小A希望自己写出的作文得分最高。当然这个计算器是有位数限制，作文长度不能超过显示位数。
计算器不能显示前导零，但是你可以添加小数点。比如作文写成“EGGODD”的话，就得按出0.00993，这个就是作文的得分，当然这得分太小了。
输入格式
第一行D表示计算器位数
第二行N表示单词数
接下来N行，一行一个单词，保证可以转换为数字。
输出格式
一行，表示最大的分值。
样例 #1
样例输入 #1
7
4
EGG
ODD
LOBE
LIBE
样例输出 #1
9933817
提示
40%数据，D<=20,N<=10
100%数据，D<=200,N<=10000,单词长度<=32
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <valarray>
using namespace std;
int n,m;
string ans;
#define N 10010
//f,v,都是string
string f[300];
int map[300];
string v[N];
int ni[N];
bool cmp(string a,string b)
{
string x=a+b,y=b+a;
return x<y;
}
void init()//打表
{
map['I']=1;map['D']=0;map['O']=0;map['q']=6;
map['G']=9;map['Z']=2;map['E']=3;map['h']=4;
map['S']=5;map['L']=7;map['B']=8;
}
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()
{
ios::sync_with_stdio(false);
cin>>m>>n;
init();
int i,j;
for (i=1;i<=n;i++)
{
string s;
cin>>s;
for (j=s.size()-1;j>=0;j--)
v[i]+=(map[s[j]]+'0');//转换后放入v[i]
}
sort(v+1,v+n+1,cmp);
for (i=1;i<=n;i++)
ni[i]=v[i].size();
for (i=n;i>=1;i--)//01背包
for (j=m;j>=ni[i];j--)
f[j]=maxs(f[j],f[j-ni[i]]+v[i]);//状态转移方程
if (f[m][0]!='0')//判断前导0
cout<<f[m];
else
{
cout<<"0.";//这里不知为何不能用printf,我用就80分
for (i=1;i<f[m].size();i++)
cout<<f[m][i];
}
return 0;
}
