题解 P2549 【计算器写作文】

zhouyihe · 2015-10-18 10:08:28 · 题解

我是贪心加dp初始化，首先如果快排之后最大的放入可行，那么一定要放入，不行再从下一个开始，用dp初始化前i个单词能否达到k的位数。然而只有50还是60分。。。小数点我没考虑但是似乎也不应该。#include<iostream>

#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#include<cstdlib>
using namespace std;
int n,m;
string ans;
bool  f[10005][205];
int match[1000];
string p[10005];
bool  comp(string x,string y)
{string s=x+y,ss=y+x;
  return s<ss;
}
void pre()
{  match['I']=1;
    match['D']=0;
    match['O']=0;
    match['q']=6;
    match['G']=9;
    match['Z']=2;
    match['E']=3;
    match['h']=4;
    match['S']=5;
    match['L']=7;
    match['B']=8;
}
void dp()
{f[0][0]=true;
   for(int i=1;i<=n;i++)
   for(int k=0;k<=m;k++)
    {if(k<p[i].size()) f[i][k]=f[i-1][k];
      else
      { f[i][k]=f[i-1][k]|f[i-1][k-p[i].size()];
      }
    }
}
void work(int x,int y)
{   if(y==0)
  {cout<<ans;
  exit(0);
  }
  if(x==0) return;
  if(y-p[x].size()>=0&&f[x-1][y-p[x].size()]==true)
   {ans=ans+p[x];
   work(x-1,y-p[x].size());
   }
  else
    work(x-1,y);
}
int main()
{ cin>>m>>n;
  pre();
    for(int i=1;i<=n;i++)
    {  string s;cin>>s;
    for(int j=s.size()-1;j>=0;j--)
       { p[i].push_back(match[s[j]]+48);
       }
    }
    sort(p+1,p+n+1,comp);
dp();
for(int i=m;i>=0;i--)
   work(n,i);
    return 0;
}