题目:http://soj.me/1001
一串数字问一共有多少种编码的可能性
思路:
code[i]为题目给出的数字(i从零开始)
当i>=2时
如果code[i]=0
case1:ans[i]=ans[i-2](因为code[i-1]不能单独存在 必须与code[i]合并,如3120,ans[1]=1,ans[2]=2,ans[3]=1)
如果code[i]!=0
如果code[i-1]=0
case2:ans[i]=ans[i-1](code[i]必须单独存在,如3102,ans[1]=1,ans[2]=1,ans[3]=1)
如果code[i-1]!=0
如果code[i-1]与code[i]合并<=26
case3:ans[i]=ans[i-1]+ans[i-2](code[i]和code[i+1]可合并也可单独分开,若合并则ans[i]=ans[i-2] 参见case1,若分开则ans[i]=ans[i-1]参见case2,如3124,ans[1]=1,ans[2]=2,ans[3]=3)
如果code[i-1]与code[i]合并>26
case4:ans[i]=ans[i-1](code[i]和code[i+1]必须分开参见case2 如code[i]=1234 ans[1]=2,ans[2]=3,ans[3]=3)
#include#include using namespace std; int main(){ string code; long long ans[100000]; int n; while (cin>>code&&code!="0") { int len=code.size(); if (len == 1) { cout << "1" << endl; continue; } n = (code[0]-'0')*10+code[1]-'0'; ans[0]=1; if (n<=26&&code[1]!='0') ans[1] = 2; else ans[1]=1; for (int i=2;i