HDU 2047 송아지 EOF 산적

제목: HDU - 2047
    제목 링크:http://acm.hdu.edu.cn/showproblem.php?pid=2047
    제목:
송아지 EOF 산적
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 28348    Accepted Submission(s): 13288
Problem Description
올해 ACM 여름 캠프 는 총 18 명 으로 6 개 팀 으로 나 뉜 다.그 중 EOF 라 는 팀 은 04 급 의 황소, XC, 05 급 의 COY 로 구성 되 어 있다.공 통 된 합숙 생활 에서 여러분 은 깊 은 우정 을 쌓 았 습 니 다. 아 우 는 열정 이 타 오 르 는 세월 을 기념 하기 위해 무엇 을 하려 고 합 니까? 생각해 보 니 아 우 는 집에 서 고급 소고 기 말 랭 이 를 가 져 왔 습 니 다. 그 위 에 n 길이 의 'E', 'O', 'F' 세 글자 로 만 구 성 된 문자열 을 새 기 려 고 합 니 다.(그 중 하나 또는 두 글자 만 있 을 수 있 지만 다른 문자 가 있어 서 는 안 된다) 아 우 는 꼬치 에 O 가 인접 한 상황 이 나타 나 는 것 을 동시에 금지한다. 그 는 'OO' 가 화 난 눈 처럼 보이 고 효과 가 좋 지 않다 고 생각한다.
당신, NEW ACMer, EOF 의 숭배자, 소 가 모두 몇 가지 요 구 를 만족 시 키 는 서로 다른 문자열 이 있 는 지 계산 해 줄 수 있 습 니까?
PS: 아 우 는 또 하나의 작은 비밀 이 있 습 니 다. 바로 EOF 가 새 겨 진 소고 기 말 린 것 을 신비 한 선물 로 항 전 50 주년 개교 기념일 에 바 치 려 고 합 니 다. 교장 선생님 이 이 소고 기 말 린 것 을 받 았 을 때 얼마나 기 뻤 을 지 상상 할 수 있 습 니 다. 여기 서 항 전 을 대표 하 는 ACMer 가 아 우 에 게 감 사 를 표 하 는 것 을 허락 해 주 십시오!
다시 한 번 감사합니다!
 
Input
입력 데 이 터 는 여러 개의 테스트 인 스 턴 스 를 포함 하고 모든 테스트 인 스 턴 스 는 한 줄 을 차지 하 며 하나의 정수 n 으로 구성 되 어 있 습 니 다. (0 < n < 40)
 
Output
모든 테스트 인 스 턴 스 에 대해 서 는 요 구 를 만족 시 키 는 도장 법 을 출력 하 십시오. 모든 인 스 턴 스 의 출력 은 한 줄 을 차지 합 니 다.
 
Sample Input

   
   
   
   
1 2

 
Sample Output

   
   
   
   
3 8

 
    이것 도 역시 푸 시 문제 입 니 다. 그리고 푸 시 관 계 를 찾 아 보 세 요!
    제한 조건 은 두 개의 O 가 서로 인접 해 서 는 안 된다 는 것 이다. f (1) 에서 f (n - 1) 까지 이미 알 고 있 는 전제 에서 f (n) 를 구 할 가치 가 있 을 때 E 또는 F 라면 그 전의 기초 위 에서 마음대로 놓 아 라. 어차피 제한 이 없다. E 와 E, F 와 F 는 같은 것 이 고 다 르 지 않 기 때문에 모두 2 * f (n - 1) 이다.만약 에 마지막 이 O 일 때 제한 조건 을 고려 해 야 한다 면 마지막 두 번 째 는 O 를 넣 을 수 없고 E 와 F 만 넣 을 수 있다. 그러면 위 와 같이 모두 2 * f (n - 2) 중의 방안 이 있 기 때문에 전달 관계 식 은 다음 과 같다.
        f(n)=2*(f(n-1)+f(n-2));
        f(1)=3;
        f(2)=8;
    코드 ~
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<math.h> 
using namespace std;
long long ans[45];
int n;
int main(){
	ans[1]=3;ans[2]=8;
	for(int i=3;i<=40;i++){
		ans[i]=(ans[i-1]+ans[i-2])*2;
	}
	while(cin>>n){
		cout<<ans[n]<<endl;
	}
	return 0;
} 

좋은 웹페이지 즐겨찾기