HDU 1267下砂の砂は何粒ありますか?
3614 ワード
砂が降った砂は何粒ありますか.
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 3587 Accepted Submission(s): 1892
Problem Description
2005年11月、私たちの学校はACM/ICCCアジア競技区成都駅の試合に参加しました.ここで、私たちは歴史的な突破を獲得しました.銅メダルですが、受賞した瞬間の興奮は、私たち何人かの心に永遠に刻まれるかもしれません.この機会を借りて、昨年ACMアジア大会に出場するために半年近く合宿に励んだベテラン選手の皆さんに感謝の意を表します.
実際、受賞以外にも、この試合の間にもう一つ記憶に残っていることがあります.それは試合当日に入場を待っていた時、ある学校の選手が「Hangzhou Dianzi Universityという学校の英語名がおもしろい」と言っているのを聞いたのです.ハハ、私たちの学校の英語名はとてもよくて、とても魅力的ですね.
しかし、事の発展は誰も予想していなかったが、杭電の英語の校名の今回の暴露に伴い、影響はますます大きくなり、多くの人が杭電の英語の校名を研究し始め、間もなく専門の研究機関を設立し、「HDU校名研究会」と呼ばれた.また、多くの有名な科学者が改行し、この問題を専門に研究しているという報道が絶えずあり、学術界では「杭電現象」と呼ばれている.多くの人が国際的に有名な定期刊行物で研究論文を発表した.その中で、特に中国のスーパー女性科学者宇春さんが書いた研究報告が最も有名で、報告はscienceに発表された.タイトルは「杭電はどうしてこんなに赤いのか」である.文の中で研究によると、Hangzhou Dianzi Universityという校名は深い哲学思想と内包を持っている.彼女は同時に大胆な推測を提出した:“1つの文字列がm個のHとn個のDから構成されると仮定して、左から右までこの列をスキャンして、もし文字Hの累計数がいつも文字Dの累計数より小さくなければ、条件を満たす文字列の総数はちょうど砂の砂粒と同じくらい多いです.”
これが今の有名な「宇春予想」です!
この予想の正しさは数学的には証明されていないが、米国側はブッシュ氏の直接の介入で、スーパーコンピューターで検証したという(1<=n<=m<1兆1000億円).my god! これはなんと偉大な推測だろう.私达は以前いつも言って、21世纪は中国に属しますが、やはりこの日がこんなに早く来るとは思っていません.夸りing...
感動と誇りのあまり、問題も来て、mとnの値が既知であれば、砂の砂粒がどれだけあるかを計算してください.
Ps:
1.中国の関係者は積極的に行動し、宇春さんのノーベル賞の申告に着手している.
2、「宇春予想」のHとDからなる文字列は現在、学術界で「杭電串」となっている(「杭電串」は先ごろ羊肉串を売る商標に登録されたが、現在、わが校は積極的に買収に連絡している.売り手の最低価格は1000万ユーロで、決して割引しないという.希望は大きくないようだ.sigh...)
Input
入力データには複数のテストインスタンスが含まれており、各行は2つの整数mとnで構成され、mとnは文字列内のHとDの個数をそれぞれ表す.我々が現在使用しているマイクロマシンは,老美のスーパーコンピュータとは比べものにならないため,問題に与えられたデータ範囲は(1<=n<=m<=20)である.
Output
各テストインスタンスについて、砂の砂粒がどれだけあるかを出力してください.計算規則は「宇春推測」を参照してください.各インスタンスの出力は1行を占めます.
Sample Input
Sample Output
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 3587 Accepted Submission(s): 1892
Problem Description
2005年11月、私たちの学校はACM/ICCCアジア競技区成都駅の試合に参加しました.ここで、私たちは歴史的な突破を獲得しました.銅メダルですが、受賞した瞬間の興奮は、私たち何人かの心に永遠に刻まれるかもしれません.この機会を借りて、昨年ACMアジア大会に出場するために半年近く合宿に励んだベテラン選手の皆さんに感謝の意を表します.
実際、受賞以外にも、この試合の間にもう一つ記憶に残っていることがあります.それは試合当日に入場を待っていた時、ある学校の選手が「Hangzhou Dianzi Universityという学校の英語名がおもしろい」と言っているのを聞いたのです.ハハ、私たちの学校の英語名はとてもよくて、とても魅力的ですね.
しかし、事の発展は誰も予想していなかったが、杭電の英語の校名の今回の暴露に伴い、影響はますます大きくなり、多くの人が杭電の英語の校名を研究し始め、間もなく専門の研究機関を設立し、「HDU校名研究会」と呼ばれた.また、多くの有名な科学者が改行し、この問題を専門に研究しているという報道が絶えずあり、学術界では「杭電現象」と呼ばれている.多くの人が国際的に有名な定期刊行物で研究論文を発表した.その中で、特に中国のスーパー女性科学者宇春さんが書いた研究報告が最も有名で、報告はscienceに発表された.タイトルは「杭電はどうしてこんなに赤いのか」である.文の中で研究によると、Hangzhou Dianzi Universityという校名は深い哲学思想と内包を持っている.彼女は同時に大胆な推測を提出した:“1つの文字列がm個のHとn個のDから構成されると仮定して、左から右までこの列をスキャンして、もし文字Hの累計数がいつも文字Dの累計数より小さくなければ、条件を満たす文字列の総数はちょうど砂の砂粒と同じくらい多いです.”
これが今の有名な「宇春予想」です!
この予想の正しさは数学的には証明されていないが、米国側はブッシュ氏の直接の介入で、スーパーコンピューターで検証したという(1<=n<=m<1兆1000億円).my god! これはなんと偉大な推測だろう.私达は以前いつも言って、21世纪は中国に属しますが、やはりこの日がこんなに早く来るとは思っていません.夸りing...
感動と誇りのあまり、問題も来て、mとnの値が既知であれば、砂の砂粒がどれだけあるかを計算してください.
Ps:
1.中国の関係者は積極的に行動し、宇春さんのノーベル賞の申告に着手している.
2、「宇春予想」のHとDからなる文字列は現在、学術界で「杭電串」となっている(「杭電串」は先ごろ羊肉串を売る商標に登録されたが、現在、わが校は積極的に買収に連絡している.売り手の最低価格は1000万ユーロで、決して割引しないという.希望は大きくないようだ.sigh...)
Input
入力データには複数のテストインスタンスが含まれており、各行は2つの整数mとnで構成され、mとnは文字列内のHとDの個数をそれぞれ表す.我々が現在使用しているマイクロマシンは,老美のスーパーコンピュータとは比べものにならないため,問題に与えられたデータ範囲は(1<=n<=m<=20)である.
Output
各テストインスタンスについて、砂の砂粒がどれだけあるかを出力してください.計算規則は「宇春推測」を参照してください.各インスタンスの出力は1行を占めます.
Sample Input
1 1
3 1
Sample Output
1
3
，
dp[i][1]=i
dp[i][j]=dp[i-1][j]+dp[i][j-1](i>=j)
dp[i][j]=0 (i<j)
#include<stdio.h>
#include<string.h>
typedef long long LL;
LL dp[21][21];
int m,n,i,j;
int main(){
for(i=1;i<=20;i++){
dp[i][1]=i;
}
for(i=1;i<=20;i++){
for(j=1;j<=20;j++){
if(i<j)
dp[i][j]=0;
else if(j!=1)
dp[i][j]=dp[i-1][j]+dp[i][j-1];
}
}
//freopen("test.txt","r",stdin);
while(~scanf("%d %d",&m,&n)){
printf("%lld
",dp[m][n]);
}
return 0;
}