전형 적 인 문제 형 (1) 리 저 호수 괴물

전형 적 인 문제 인 리 저 호수 괴물 을 전달 하 다.
  • 원제 링크 북 사 OJ
  • https://oj.bnuz.edu.cn/
  • 피 보 나치 수열 과 유사 한 문제
  • 북 사 OJ
    https://oj.bnuz.edu.cn/
    이 문 제 는 북 사주 에 여 택 호수 괴물 이 있 고 작은 물 괴물 은 4 년 째 부터 매년 새로운 물 괴물 을 낳 을 수 있 으 며 물 괴물 은 걸 리 지 않 는 다 는 뜻 이다.
    이것 은 피 보 나치 수열 과 유사 한 문제 이다.
    '신규' 인원 을 어떻게 이해 하 느 냐 에 중점 을 둔 것 은 3 년 전 살 아 있 던 물괴 수 를 4 년 째 부터 계산 하 는 것 입 니 다. 4 년 째 fib (n - 3) 가 의미 가 있 기 때 문 입 니 다. longlong 과 길 어 지 는 배열 을 사용 해 야 합 니 다. fib 55 가 이미 많 기 때 문 입 니 다. 단순 한 재 귀 로 하면 공간 과 시간 이 폭발 할 수 있 습 니 다. fib (55) 로 인해 fi2 pow 55 의 연산 횟수 가 발생 할 수 있 습 니 다.대량의 낭비 연산 과 동시에 fib (55) 를 계산 하기 위해 불필요 한 공간 최 악의 결 과 를 동시에 개척 해 야 합 니 다. 50 여 개의 스 택 이 동시에 존재 할 수 있 기 때문에 우 리 는 전달 하 는 방법 을 취 합 니 다.
    
    #include
    using namespace std;
    long long a[58];
    int main(int argc, const char * argv[])
    {
    	a[1]=1;
    	a[2]=2;
    	a[3]=3;
    	for(int i=4;i<=55;i++)
    	{
    		a[i]=a[i-1]+a[i-3];
    	}
    	int in;
    	cin>>in;
    //	//               ,                 
    //	vector inp;//         
    //	inp[0]=-1;//             ;
    //	while(in)
    //	{
    //		inp.push_back(in);
    //		cin>>in;
    //	}
    //	for(int i=1;;i++)
    //	{
    //		cout<>in;
    }
    return 0;
    }

    좋은 웹페이지 즐겨찾기