1001. Alphacode (sicily)

Description
    Alice and Bob need to send secret messages to each other and are discussing ways to encode their messages: Alice: "Let's just use a very simple code: We'll assign `A' the code word 1, `B' will be 2, and so on down to `Z' being assigned 26."Bob: "That's a stupid code, Alice. Suppose I send you the word `BEAN' encoded as 25114. You could decode that in many different ways!"Alice: "Sure you could, but what words would you get? Other than `BEAN', you'd get `BEAAD', `YAAD', `YAN', `YKD' and `BEKD'. I think you would be able to figure out the correct decoding. And why would you send me the word `BEAN' anyway?"Bob: "OK, maybe that's a bad example, but I bet you that if you got a string of length 500 there would be tons of different decodings and with that many you would find at least two different ones that would make sense."Alice: "How many different decodings?"Bob: "Jillions!"For some reason, Alice is still unconvinced by Bob's argument, so she requires a program that will determine how many decodings there can be for a given string using her code.
Input
Alice와 Bob은 서로 비밀 정보를 전달해야 하며, 그들은 그들의 정보를 어떻게 인코딩하는지 토론하고 있다.
Alice: "우리는 아주 간단한 인코딩을 사용하자. 우리는 'A' 를 1, 'B' 를 2로 간주하고, 'Z' 를 26으로 추정한다."
Bob: "그건 어리석은 인코딩이야, 앨리스. 만약 내가'BEAN'을 보낸다면, 인코딩은 25114야. 너는 여러 가지 다른 방식으로 인코딩할 수 있어!"
Alice: "물론 다른 방식으로 디코딩을 할 수 있지만 어떤 단어를 얻을 수 있을까요?'BEAN'을 제외하고는'BEAD','YAAD','YAN','YKD','BEKD'를 얻을 수 있을 것 같아요. 정확한 디코딩을 찾을 수 있을 것 같아요. 그런데 왜'BEAN'을 보낼 수 없을까요?"
Bob: "그래, 그게 좋은 예가 아닐지도 몰라. 하지만 내가 감히 내기할게. 만약에 길이가 500인 인코딩을 받으면 톤에 달하는 다른 인코딩이 있을 거야. 그러면 의미 있는 인코딩만 찾을 수 없을 거야."
Alice: "몇 가지 다른 디코딩이 있습니까?"
Bob: "셀 수 없이 많아요!"
Alice는 일부 이유로 Bob에 의해 설득되지 않았기 때문에, 특정한 인코딩에 대해 몇 가지 디코딩 방식이 있는지 결정하는 프로그램이 필요하다.
    Input will consist of multiple input sets. Each set will consist of a single line of digits representing a valid encryption (for example, no line will begin with a 0). There will be no spaces between the digits. An input line of `0' will terminate the input and should not be processed
Output
    For each input set, output the number of possible decodings for the input string. All answers will be within the range of a long variable.
샘플 가져오기
    25114
    1111111111
    3333333333
    0
출력 예제
    6
    89
    1
코드 구현(문자열이 처리되어 시간이 1s의 요구를 만족시키지 못함)

  1 #include <stdlib.h>
  2 #include <iostream>
  3 #include <string>
  4 using namespace std;
  5 #define MAX 10000
  6 int totalCount(string a);
  7 int main()
  8 {
  9     string temp;
 10     long sets[MAX]={0};
 11     int point=0;
 12     while(cin>>temp&&temp!="0")
 13     {
 14          int result=0;
 15          //    ——        、  、       
 16          if(temp.length()==1)
 17          {
 18              sets[point]=1;
 19              point++;
 20              continue;
 21          }
 22          else
 23          {
 24              string abc1="";
 25              string abc2="";
 26              for(int i=1;i<temp.length();i++)
 27              {
 28                      abc1+=temp[i];
 29                      if(i!=1)
 30                      {
 31                          abc2+=temp[i];   
 32                      }     
 33              }
 34              
 35              int ii=(temp[0]-'0')*10+(temp[1]-'0');
 36              if(ii!=10)
 37              {
 38                  result+=totalCount(abc1);
 39              }
 40              //cout<<"   "<<temp[0]<<temp[1]<<ii<<endl;
 41              if(ii>9&&ii<27)
 42              {
 43                   result+=totalCount(abc2);
 44              }
 45              sets[point]=result;
 46              point++;
 47          }
 48          
 49           
 50     }
 51     bool flag=true;
 52     for(int i=0;i<MAX&&flag;i++)
 53     {
 54          if(sets[i]!=0)
 55          {
 56               cout<<sets[i]<<endl;
 57               
 58          }
 59          else
 60          {
 61              flag=false;
 62          }
 63     }
 64     system("pause");
 65     return 0;
 66 }
 67 int totalCount(string a)
 68 {
 69     if(a==""||a.length()==1)
 70     {
 71         return 1;               
 72     }
 73     int count=0;
 74 
 75     int b=(a[0]-'0')*10+(a[1]-'0');
 76     if(b!=10)
 77     {
 78         string abc="";
 79         for(int i=1;i<a.length();i++)
 80         {
 81                 abc+=a[i];
 82         }
 83         count+=totalCount(abc);
 84     }
 85     if(b!=10)
 86     {
 87     }
 88     //cout<<"   "<<b<<endl;
 89     if(b<27&&b>9)
 90     {
 91         string abc="";
 92         for(int i=2;i<a.length();i++)
 93         {
 94                 abc+=a[i];
 95         }
 96         count+=totalCount(abc);
 97     }
 98     //cout<<"   "<<count<<endl;
 99     return count;
100 }

 
버전 커밋

 1 //#include <stdlib.h>
 2 #include <iostream>
 3 #include <string>
 4 #define MAX 100000
 5 using namespace std;
 6 int main()
 7 {
 8     long long array[MAX];
 9     string str;
10     int size;
11     while(cin>>str&&str!="0")
12     {
13         size=str.length();
14         if(size==1)
15         {
16             cout << "1" << endl; 
17             continue;
18         } 
19         else
20         {
21             array[0]=1; 
22             for(int i=1;i<size;i++)
23             {
24                  int flag=(str[i-1]-'0')*10+(str[i]-'0');
25                  if(i==1)
26                  {
27                      if(str[i]=='0'||flag<10||flag>26)
28                      {
29                           array[i]=array[i-1];
30                      }
31                      else
32                      {
33                          array[i]=2;
34                      }
35                  }
36                  else
37                  {
38                      
39                      if(str[i]=='0')
40                      {
41                           array[i]=array[i-2];
42                           array[i-1]=array[i-2];
43                      }
44                      else if(flag<10||flag>26)
45                      {
46                          array[i]=array[i-1];
47                      }
48                      else
49                      {
50                          array[i]=array[i-1]+array[i-2];
51                      }
52                  }
53             }
54         }
55         cout << array[size-1] << endl; 
56     }
57     return 0;
58 }