HDU 2047 송아지 EOF 산적
제목 링크: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;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[HDU] 4089 활성화 확률 DPdp[i][j]를 모두 i개인의 대기열인 Tomato가 j위 서버가 마비될 확률로 역추를 사용하면 우리는 상태 이동 방정식을 얻을 수 있다. i == 1 : dp[1][1] = dp[1][1] * p1 + dp[1]...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.