모래 가 내 려 오 는 모래 는 몇 알 입 니까?(hdu 1267) 전달

모래 가 내 려 오 는 모래 는 몇 알 입 니까?
Time Limit : 2000/1000ms (Java/Other)   Memory Limit : 65536/32768K (Java/Other)
Total Submission(s) : 1   Accepted Submission(s) : 1
Problem Description
2005 년 11 월 에 우리 학 교 는 ACM/ICPC 아시아 경기 구 청 두 역 경기 에 참 가 했 습 니 다. 여기 서 우 리 는 역사적 인 돌 파 를 얻 었 습 니 다. 비록 동메달 이지 만 상 을 받 는 순간 의 흥분 은 우리 몇 사람의 마음 에 영원히 새 겨 질 것 입 니 다.이번 기회 에 지난해 ACM 아시 안 게임 출전 을 위해 반년 가까이 힘 들 게 합숙 훈련 을 한 베테랑 선수 여러분 께 특별히 감 사 를 드 립 니 다.실제로 수상 외 에 도 이번 대회 기간 에 기억 에 남 는 것 이 하나 더 있다.경기 당일 입장 을 기다 리 던 중 어느 학교의 한 선수 가 "학교 영어 이름 이 재 미 있 는데 항 저 우 다이 안 지 유 니 버 시 티 라 니 요?"라 고 말 하 는 것 을 들 었 다. 하하, 우리 학교 영어 이름 이 아주 잘 지 어 졌 나 봐 요. 아주 매력 적 이 었 나 봐 요.그러나 일의 발전 은 아무 도 예상 하지 못 했다. 항 저 우 전 영문 학명 이 이번에 밝 혀 지면 서 영향 이 점점 커지 면서 많은 사람들 이 항 저 우 전 영문 학명 에 대해 연 구 를 하기 시 작 했 고 얼마 후 에는 'HDU 학명 연구회' 라 는 전문 연구 기 구 를 설립 하기 도 했다.그리고 상 - 당 - 다 의 유명 과학자 들 이 이 문 제 를 전문 적 으로 연구 하고 학계 에서 '항 전 현상' 이 라 고 부른다 는 보도 가 끊 이지 않 았 다.많은 사람들 이 국제 유명 간행물 에 연구 논문 을 발표 했다. 그 중에서 특히 중국 슈퍼 여성 과학자 우 춘 양 이 쓴 연구 보고서 가 가장 유명 하 다. 보고 서 는 science 에 발표 되 었 다. 제목 은 '항 저 우 전기 가 왜 이렇게 빨 갛 습 니까?' 라 는 글 에서 항 저 우 Dianzi University 라 는 학교 이름 은 깊 은 철학 사상 과 의 미 를 가진다.그 는 "하나의 문자열 이 m 개의 H 와 n 개의 D 로 구성 되 어 있다 고 가정 하고 왼쪽 에서 오른쪽으로 이 문자열 을 스 캔 한다. 만약 에 문자 H 의 누적 수가 문자 D 의 누적 수 보다 적지 않 으 면 조건 을 만족 시 키 는 문자열 의 총 수 는 모래 알갱이 만큼 많다"고 대담 한 추측 을 제기 했다. 이것 이 바로 현재 의 유명한 '우 춘 추측' 이다.아직 수학 적 으로 이 추측의 정확성 을 증명 하 지 는 못 했 지만 미국 측은 부시 대통령의 직접 개입 으로 슈퍼 컴퓨터 로 (1 < = n < = m < = 1000000000) 때 모두 정확 하 다 는 것 을 검증 했다 고 한다.my god! 이것 은 얼마나 위대 한 추측 인가!우 리 는 예전 에 항상 21 세 기 는 중국의 것 이 라 고 말 했 지만 이날 이 이렇게 일찍 올 줄 은 몰 랐 습 니 다. 자 랑스 러 움.. + 감동 ing... 감동 과 자 랑스 러 움 의 나머지 문제 도 생 겼 습 니 다. m 와 n 의 값 을 알 고 있다 면 모래 알갱이 가 얼마나 되 는 지 계산 해 보 세 요.Ps: 1. 중국 관련 측은 적극적으로 움 직 여 우 춘 양 에 게 노벨상 신 고 를 하고 있 습 니 다.2. '우 춘 추측' 에서 언급 한 H 와 D 로 구 성 된 문자열 은 현재 학계 에서 '항 저 우 꼬치' 가 되 었 다.
 
Input
입력 데 이 터 는 여러 개의 테스트 인 스 턴 스 를 포함 하고 각각 한 줄 을 차지 하 며 두 개의 정수 m 와 n 으로 구성 되 며 m 와 n 은 문자열 의 H 와 D 의 개 수 를 표시 합 니 다.현재 우리 가 사용 하고 있 는 마이크로컴퓨터 와 노 미의 슈퍼 컴퓨터 는 비교 할 수 없 기 때문에 제목 이 정 한 데이터 범 위 는 (1 < = n < = m < 20) 이다.
 
Output
모든 테스트 인 스 턴 스 에 대해 모래 를 출력 하 는 모래알 이 얼마나 되 는 지 계산 규칙 은 '우 춘 추측' 을 참고 하 십시오. 모든 인 스 턴 스 의 출력 은 한 줄 을 차지 합 니 다.
 
Sample Input

   
   
   
   

    
    
    
    1 1
3 1

   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    1
3

   
   
   
   

 
 
 
사고: f [m] [n] = f [m] [n - 1] + f [m - 1] [n].
        f [m] [n] = f [m] [n - 1] 뒤에 D + f [m - 1] [n] 뒤에 H 추가;
 
 
전재 출처 를 밝 혀 주세요: 찾 아 라 & 밤하늘 의 아이
 
제목 링크:http://acm.hdu.edu.cn/showproblem.php?pid=1267
 

#include<stdio.h>
#define LL __int64
LL num[25][25];
void init()
{
    for(int i=1;i<=20;i++)
    {
        num[i][0]=1;
        for(int j=1;j<i;j++)
            num[i][j]=num[i][j-1]+num[i-1][j];
        num[i][i]=num[i][i-1];
    }
}
int main()
{
    int m,n;
    init();
    while(scanf("%d%d",&m,&n)!=EOF)
    {
        if(m<n) printf("0
");
        else printf("%I64d
",num[m][n]);
    }
    return 0;
}