1002.cpp

我的URAL的1000 ~ 1050 的全部代码 包含WA 最后AC的程序 有2~3个比较难的是MAIGO的程序

// dp f[i] = min(f[i - len[k] ])+1 k为1～20
#include <iostream>
#include <string>
#include <vector>
using namespace std;

//数字 -->字母的替换 1 ij	2 abc	3 def 4 gh	5 kl	6 mn 7 prs	8 tuv	9 wxy 0 oqz
//              abcdefghijklmnopqrstuvwxyz
string check = "22233344115566070778889990";
string numStr;				//数字串
int f[101];					//表示第i-1个字母...的值
int n;
vector <string> strArr, bak;
int path1[101],path2[101],pre[101];	//path1 numStr 路径 path2 第几个单词

int min( int a, int b ){ return a < b ? a : b;} 
void work()
{
	int i, j, k;
	int l = numStr.length();
	bool flag = false;
	memset(f,0, sizeof(f));
	memset(path1,0,sizeof(path1));
	memset(path2,0,sizeof(path2));
	f[0] = 1;
	for( i = 1 ; i <= l; i++ )
		for( j = 0; j < n; j++ )
		{
			flag = true;
			if( ( i - strArr[j].length() ) >= 0 && f[ i - strArr[j].length() ] > 0 )
			{
				for( k = i - strArr[j].length(); k < i; k++ )
					if( numStr[k] != strArr[j][ k-i+strArr[j].length() ] ){flag = false ; break;}
			}
			else
				flag =false;
			if ( flag && (f[i]==0 || f[i] > f[i - strArr[j].length() ]) )
			{
				f[i] = f[ i - strArr[j].length() ] + 1;
				path1[i] = i - strArr[j].length();
				path2[i] = j;
			}
		}
		k = l;
		if( f[k] == 0 ) cout << "No solution." << endl;
		else
		{
			for( i = 1; i < f[l]; i++)
			{
				pre[i] = k;
				k  = path1[k];
			}
			for( i = f[l] - 1; i >= 1; i-- )
				cout << bak[ path2[ pre[i] ] ] << ' ';
			cout << endl;
		}
}

int main()
{
	int i,j;
	while(cin >> numStr,numStr[0]!='-')
	{
		cin >> n;
		string temp;
		for( i = 0; i < n; i++ )
		{
			cin >> temp;
			strArr.push_back(temp);
			bak.push_back(temp);
			for( j = 0; j < strArr[i].length(); j++ )
				strArr[i][j] = check[ strArr[i][j]-'a' ];
		}
		work();
	}
	return 0;
}