xiaoguozi's Blog
Pay it forword - 我并不觉的自豪,我所尝试的事情都失败了······习惯原本生活的人不容易改变,就算现状很糟,他们也很难改变,在过程中,他们还是放弃了······他们一放弃,大家就都是输家······让爱传出去,很困难,也无法预料,人们需要更细心的观察别人,要随时注意才能保护别人,因为他们未必知道自己要什么·····
今天做ural 1002,题目描述:
1002. Phone numbers
Time Limit: 2.0 second
Memory Limit: 16 MB

Background

In the present world you frequently meet a lot of call numbers and they are going to be longer and longer. You need to remember such a kind of numbers. One method to do it in an easy way is to assign letters to digits as shown in the following picture:

	1 ij	2 abc	3 def
4 gh	5 kl	6 mn
7 prs	8 tuv	9 wxy
0 oqz
This way every word or a group of words can be assigned a unique number, so you can remember words instead of call numbers. It is evident that it has its own charm if it is possible to find some simple relationship between the word and the person itself. So you can learn that the call number 941837296 of a chess playing friend of yours can be read as WHITEPAWN, and the call number 2855304 of your favourite teacher is read BULLDOG.

 

Problem

Write a program to find the shortest sequence of words (i.e. one having the smallest possible number of words) which corresponds to a given number and a given list of words. The correspondence is described by the picture above.

Input

Input contains a series of tests. The first line of each test contains the call number, the transcription of which you have to find. The number consists of at most 100 digits. The second line contains the total number of the words in the dictionary (maximum is 50000). Each of the remaining lines contains one word, which consists of maximally 50 small letters of the English alphabet. The total size of the input file doesn't exceed 300KB. The last line of input file contains call number -1.

Output

Each line of output contains the shortest sequence of words which has been found by your program. The words are separated by single spaces. If there is no solution to the input data, the line contains text "No solution.". If there are more solutions having the minimum number of words, you can choose any single one of them.

Sample

input
output
7325189087
            5
            it
            your
            reality
            real
            our
            4294967296
            5
            it
            your
            reality
            real
            our
            -1
            
reality our
            No solution.
            


思路就是dp,状态转移是dp[i]=min(dp[i-len[j]]+1)(1<=j<=n)
code:
#include <iostream>
#include 
<string>
#include 
<algorithm>
#include 
<stack>
#include 
<vector>

using namespace std;
//#pragma comment(linker, "/STACK:16777216")

const int N=105;
const int M=50001;
int dp[N];
int pathone[N];
int pathtwo[N];
int hash[26]={2,2,2,3,3,3,4,4,1,1,5,5,6,6,0,7,0,7,7,8,8,8,9,9,9,0};
vector
<string> vec,v;
vector
<int> ve;
void Init()
{
    memset(dp,
0,sizeof(dp));
    memset(pathone,
0,sizeof(pathone));
    memset(pathtwo,
0,sizeof(pathtwo));
    vec.clear();
    v.clear();
    ve.clear();
};
int main()
{
    
string ss;
    
while(cin>>ss){
        
if(ss=="-1")break;
        Init();
        
int n;
        cin
>>n;
        
string str;
        
for(int i=0;i<n;i++){
            cin
>>str;
            v.push_back(str);
            
string tmp;
            
for(int j=0;j<str.size();j++){
                tmp
+=hash[str[j]-'a']+48;
            }
            vec.push_back(tmp);
        }
        dp[
0]=1;
        
for(int i=1;i<=ss.size();++i){
            
for(int j=0;j<vec.size();++j){
                
if(i-vec[j].size()>=0&&dp[i-vec[j].size()]>0){
                                   
if(vec[j]==ss.substr(i-vec[j].size(),vec[j].size())&&(dp[i]==0||dp[i]>dp[i-vec[j].size()]+1)){
                        dp[i]
=dp[i-vec[j].size()]+1;
                        pathone[i]
=j;
                        pathtwo[i]
=i-vec[j].size();
                    }
                }
            }
        }
        
if(dp[ss.size()]==0){
            cout
<<"No solution.\n";
        }
        
else{
            
int mm=ss.size();
            
//ve.push_back(mm);
            while(mm!=0){
                
//stk.push(v[pathone[mm]]);
                ve.push_back(mm);
                mm
=pathtwo[mm];
                
            }
            
for(int i=ve.size()-1;i>=0;i--){
                
if(i==ve.size()-1)cout<<v[pathone[ve[i]]];
                
else cout<<" "<<v[pathone[ve[i]]];
            }
            cout
<<endl;
        }
    }
    
return 0;
}
以上code ,(Crash), 看了FAQ,相当于STACK_OVERFLOW ,先是郁闷。。。。
玩了花了N多时间查找哪错问题了。。。。
没办法时加了句 i-vec[j].size()<N于是奇迹出现了Accepted.....汗
于是想问下各位路过大牛,,题目明显是i<N,i-vec[j].size()<N不是就成了句废话了。。。。无语.....
我碰到类似dp,用dp[i+len[j]]>dp[i]+1 dp[i+len[j]]=dp[i]+1转换下,就不会出现此问题,,而用dp[i-len[j]]+1<dp[i],dp[i]=dp[i-len[j]]+1问题就出现了。。。RE,所以想问下原因,,,我以保证i-len[j]>=0&&i-len[j]<N(dp[N])
posted on 2008-04-05 16:21 小果子 阅读(276) 评论(0)  编辑 收藏 引用 所属分类: Acm

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理