1410121949-hd-1sting

1sting

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

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

題目大意 你會得到一個字符串只包含“1”；你可以合並兩個相鄰的‘1’變為‘2’。當然，你可能會得到很多不同的結果。例如，你可以得到1111，1111，121，112211,22。現在，你的工作是找到這個字符串的結果最多種類數。

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.

第一行是一個數n指的是測試用例的數目。然後N線以下，每行有一個由1個字符串。序列的最大長度為200。

錯誤原因

一開始發現了這是斐波那契數列，也想到了用int64位，但是范圍仍然不夠，好吧，原諒我沒想到會和大數加減結合。大數加減這一塊自己也掌握的不好。還有用if之後，會習慣性忘記else這一情況。

代碼

#include
#include
char s[230];
int num[230][1000];
int len[1000];
//int len[100];  數組開小了。 
int main()
{
	//這道題是斐波那契數列和大數加減法的結合 
	int n;
	int i,j,k,l,m;
	memset(num,0,sizeof(num));
	//二維數組也可以這樣初始化。 
	num[1][0]=1;
	num[2][0]=2;
	len[1]=len[2]=1;
	l=0;
	for(i=3;i<210;i++)
	{
		k=0;
		for(j=0;j<=len[i-1];j++)
		{
			l=k+num[i-1][j]+num[i-2][j];
			num[i][j]=l%10;
			k=l/10;
		}
	//需要定義l,k兩個變量。 
		if(num[i][len[i-1]]!=0)
		    len[i]=len[i-1]+1;
		else//else老是忘記，這兒出錯了 
		    len[i]=len[i-1];
	}
	//因為200位呢，需要用大數。 
	scanf("%d",&n);
	getchar();
	while(n--)
	{
		scanf("%s",s);
		m=strlen(s);
		for(i=len[m]-1;i>=0;i--)
		    printf("%d",num[m][i]);
		printf("\n");
	}
	return 0;
}