zjut1676搭数字I

http://acm.zjut.edu.cn/ShowProblem.aspx?ShowID=1676

/*
搭数字I 
Time Limit:1000MS  Memory Limit:32768K
Description:

楠哥哥是个小屁孩，喜欢玩筷子。有天他发现若干根筷子可以搭成一些数字。如图

（搭出数字1需要两个筷子，数字2需要5根筷子……）
现在就有疑问了，给定n（2<=n<100）根筷子，那个可以组成的最小数是多少？
Input:

每行给定一个筷子数量n （2<=n<100）
Output:

每行输出用这n根筷子所能组成的最小数。
Sample Input:

3
6
7
15
Sample Output:

7  
0  
8  
108
Brute force
我最初是用DFS做的，结果run到35就异常的艰难 效率实在是低下啊， 后来通过可以已有的run出来的结果我找
到了规律 在n=15以后结果呈现规律 n=15到21为第一组，后面的结果均为第一组相应数字尾部加8  即满足
num[i]=num[i-7]+'8';
*/
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int n,m;
string ans;
int chop[11]={6,2,5,5,4,5,6,3,7,6};
string num[101];
bool cmp(string a,string b)
{
	if(a.size()<b.size())return 1;
	if(a<b)return 1;
	return 0;
}
void DFS(string s,int cost)
{
	if(cost>m)return;
	if(s[0]=='0'&&s.size()>1)return;
	if(s.size()>15)return;
	if(cost==m)
	{
        if(cmp(s,ans))ans=s;
		return;
	}
	for(int i=0;i<9;i++)
	{
		if(i==3||i==5||i==9)continue;
		if(s.size()>1&&(i==7||i==4))continue;
		char ch=i+'0';
		DFS(s+ch,cost+chop[i]);
	}
}
void pre()
{
	for(int i=0;i<=21;i++)
	{
		ans=string(15,'9');
		m=i;
        DFS("",0);
		num[i]=ans;
	}
	for(int i=22;i<=100;i++)
	{
		num[i]=num[i-7]+'8';
	}
}
int main()
{
     pre();
     while(cin>>n)
	 {
        
		 cout<<num[n]<<endl;
	 }
}