首页 > 代码库 > HDU 1865

HDU 1865

2024-07-14 05:18:15   220人阅读

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
311111111
 

 

Sample Output
128
 

 

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();

OK

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--;        }    }}

 

HDU 1865


联系
我们