hdu 2563-통계 문제[전달 관계]

통계 문제
Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 6525    Accepted Submission(s): 3843
링크:hdu 2563
Problem Description
무한대 의 2 차원 평면 에서 우 리 는 다음 과 같은 가설 을 한다.
1、  매번 한 칸 만 이동 가능;
2、  뒤로 가면 안 됩 니 다.
3、  지나 간 칸 이 바로 내 려 앉 아 두 번 다시 갈 수 없 음;
n 보 의 다른 방안 수(2 가지 방법 은 한 걸음 만 다 르 면 다른 방안 으로 여 겨 진다)를 구한다.
 
Input
먼저 정수 C 를 제시 하여 C 조 테스트 데이터 가 있 음 을 나타 낸다.
다음 C 줄 은 줄 마다 정수 n(n<20)을 포함 하여 n 걸음 을 가 겠 다 는 뜻 입 니 다.
 
Output
n 단계 의 다른 프로젝트 의 총 수 를 프로 그래 밍 하 십시오.
각 그룹의 출력 이 한 줄 을 차지한다.
 
Sample Input

   
   
   
   

    
    
    
    2
1
2
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    3
7
   
   
   
   

 
제목:  중국어 제목,제목 이 여기에 놓 여 있 으 니 말 하지 않 겠 습 니 다~~~
분석:
이 문제 시합 을 할 때 나 는 어떤 전달 관 계 를 생각 하지 않 았 다.분명 하 다.데이터 가 크 지 않 아서 나 는 충분히 시 계 를 칠 수 있다.사실 나 는 이 문 제 는 dfs 가 시 계 를 친 적 이 있다.1A 는 FB 를 얻 은 후에 경기 후에 타 표 데 이 터 를 보고 나 서 야 전달 관 계 를 발견 했다.zZ。

//    
int vis[50][60];
void DFS(int x, int y, int step)
{
    if(step == N)
    {
        ans++;
        return;
    }
    if(!vis[x - 1][y])
    {
        vis[x - 1][y] = 1;
        DFS(x - 1, y, step + 1) ;
        vis[x - 1][y] = 0;
    }
    if(!vis[x][y - 1])
    {
        vis[x][y - 1] = 1;
        DFS(x, y - 1, step + 1);
        vis[x][y - 1] = 0;
    }
    if(!vis[x][y + 1])
    {
        vis[x][y + 1] = 1;
        DFS(x, y + 1, step + 1);
        vis[x][y + 1] = 0;
    }
}

/****************************>>>>HEADFILES<<<<****************************/
#include <set>
#include <map>
#include <list>
#include <cmath>
#include <queue>
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
using namespace std;
/****************************>>>>>DEFINE<<<<<*****************************/
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#define FIN             freopen("input.txt","r",stdin)
#define FOUT            freopen("output.txt","w",stdout)
#define CASE(T)         for(scanf("%d",&T);T--;)
typedef __int64 LL;
/****************************>>>>SEPARATOR<<<<****************************/
//    
int ans[] = {0,3,7,17,41,99,239,577,1393,3363,8119,19601,47321,114243,275807,665857,1607521,3880899,9369319,22619537,54608393,131836323};
int N,T;
int main()
{
    //FIN;
    CASE(T)
    {
        scanf("%d",&N);
        printf("%d
",ans[N]);
    }
    return 0;
}

비교 데 이 터 를 통 해 ans[i]=ans[i-1]*2+ans[i-2]발견  ..... haha