计算器写作文

一起来交流编程吧【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;
}