【杭电oj】1865 - 1sting（大数递推）

点击打开题目 1sting

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

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杭电集训队选拔赛——热身赛

观察了一下，就是大数的斐波那契数列。

代码如下：

#include <cstdio>
#include <cstring>
int main()
{
	int k,u,n;
	char num[211];
	int fi[1011][151] = {0};
	fi[0][1] = 1;
	fi[1][1] = 1;
	for (int i = 2 ; i <= 1000 ; i++)
	{
		for (int j = 1 ; j <= 150 ; j++)
		{
			fi[i][j] += fi[i-1][j] + fi[i-2][j];
			if (fi[i][j] >= 10)
			{
				fi[i][j] -= 10;
				fi[i][j+1]++;
			}
		}
	}
	scanf ("%d",&u);
	while (u--)
	{
		scanf ("%s",num);
		n = strlen(num);
		k = 150;
		for ( ; fi[n][k] == 0 ; k--);
		for ( ; k >= 1 ; k--)
			printf ("%d",fi[n][k]);
		printf ("\n");
	}
	return 0;
}