HDU 1865 1sting （递推、大数）

发布时间：2020-12-14 05:10:29 所属栏目：大数据来源：网络整理

导读：1sting Time Limit: 5000/1000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 7573????Accepted Submission(s): 2945 ? Problem Description ? You will be given a string which only contains ‘1’; You can merg

1sting

Time Limit: 5000/1000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 7573????Accepted Submission(s): 2945

Problem Description

You will be given a string which only contains ‘1’; You can merge two adjacent ‘1’ to be ‘2’,or leave the ‘1’ there. Surly,you may get many different results. For example,given 1111,you can get 1111,121,112,211,22. Now,your work is to find the total number of result you can get.

Input

The first line is a number n refers to the number of test cases. Then n lines follows,each line has a string made up of ‘1’ . The maximum length of the sequence is 200.

Output

The output contain n lines,each line output the number of result you can get .

Sample Input

Sample Output

1
2
8

题目大意

给你一个仅包含‘1‘的字符串; 你可以将两个相邻的“1”合并为“2”，或将“1”保留。例如，给定1111，可以获得1111,22。要求计算出可能的结果数量。

题目分析

当只有一个‘1’的时候，只有一种情况

　　有两个‘1’的时候，有两种情况，一种是 11 一种是 2

　　n>2的时候，我们可以在n-1的基础上在字符串的末尾加上一个 1

　　　　　　　　　　也可以在n-2的基础上加上一个2

所以得出递推公式：
　　f(n) = f(n-1) + f (n-2)

代码

#include<bits/stdc++.h>

using namespace std;

int n,i;
string x;
string bigadd(string a,string b)
{
    int jin=0,i;
    char ai,bi;
    string anss=a;
    int lena=a.size();
    int lenb=b.size();
    int lenmax=max(lena,lenb);
    int p=lena-1;
    int q=lenb-1;
    for(i=lenmax-1;i>=0;i--)
    {
        if(p<0)
        ai=‘0‘;
        else
        ai=a[p];
        if(q<0)
        bi=‘0‘;
        else
        bi=b[q];
        anss[i]=((ai-‘0‘+bi-‘0‘+jin)%10)+‘0‘;
        jin=(ai-‘0‘+bi-‘0‘+jin)/10;
        p--;
        q--;
    }
    if(jin)
    {
        char x=jin+‘0‘;
        anss=x+anss;
    }
    return anss;
}
 int main()
 {  
    string a[205];  
    a[1]="1";  
    a[2]="2";   
    for(i=3;i<205;++i)  
           a[i]=bigadd(a[i-1],a[i-2]);  
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        cin>>x;
        cout<<a[x.size()]<<endl; 
    }
    return 0;       
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!