HDU 1865

1sting

Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3200 Accepted Submission(s): 1230

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

3 1 11 11111

Sample Output

1 2 8

Author

z.jt

Source

2008杭电集训队选拔赛——热身赛

简单的动态规划

结果是斐波那契数列

分析：

假设长度为n的数字结果为f(n)

则f（n+1）有两种可能

1，合并后末尾依旧为1，则种类为f（n）

2，合并后末尾为2，则总类为f（n-1）

所以：f（n+1）=f（n）+f（n-1）；

然后最大长度为200

直接用c++

long long 都存不下

看到java里有BigInteger类

打算来用Java玩玩

注意主类命名为Main

不能直接加，改为add

不能直接赋值，调用valueOf();

import java.math.BigInteger;
import java.util.Scanner;


public class Main {
    public static void main(String args[])
    {
        Scanner input = new Scanner(System.in);
        BigInteger ans[] = new BigInteger[201];
        ans[0] = BigInteger.valueOf(1);;
        ans[1] = BigInteger.valueOf(1);;
        for(int i = 2;i<201;i++)
        {
              ans[i]=ans[i-1].add(ans[i-2]);
        }
        int T=input.nextInt();
        while(T!=0)
        {
            String str = input.next();
            int len = str.length();
            System.out.println(ans[len]);
            T--;
        }
    }

}