Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:超时啊!!!!!!!!!那位大虾帮帮,看看出了什么问题

Posted by Web_Board at 2011-03-16 10:24:56 on Problem 1953
In Reply To:超时啊!!!!!!!!!那位大虾帮帮,看看出了什么问题 Posted by:19850317 at 2007-08-28 17:27:45
> 代码:
> #include "iostream.h"
> int fib(int t);
> int main()
> {
> 	int i;
> 	while (cin>>i)
> 	{
> 		int a[10000];
> 		for(int k=0;k<i;k++)
> 		{
> 			cin>>a[k];
> 			cout<< "Scenario #"<<k+1<<' '<<":"<<endl;
> 			cout<<fib(a[k])<<endl;
> 		}
> 		
> 	}
> 	return 0;
> }
> fib(int t)
> {
>     if(t==1)return 2;
> 	else if(t==2)return 3;
>     else
> 		return (fib(t-1)+fib(t-2));
> }
你这个不超时还真是目有天理啊。。。。n的算法被写成了2^n,在fib函数里面打个表就变成n的DP了。
#include <stdio.h>

int Fib(int fi_num)
{
	static int StateList[50] = {0,2,3};
	return StateList[fi_num] ? StateList[fi_num] : StateList[fi_num] = Fib(fi_num - 1) + Fib(fi_num - 2);
}

int main()
{
	int n,t;
	scanf("%d",&n);
	for(int i = 1;i <= n;i ++)
	{
		scanf("%d",&t);
		printf("Scenario #%d:\n%d\n\n",i,Fib(t));
	}
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator