題目網址：??? http://acm.hdu.edu.cn/game/entry/problem/show.php?chapterid=2&sectionid=3&problemid=9

分析，這題其實是H和D的組合排列問題，只不過要考慮期間累計的H和D的數量關系。

用DP來做，可以推導出：

dp[i][j] = dp[i-1][j] + dp[i][j-1]

dp[][]前一個表示H的數量，后一個表示D的數量。

分上面那種情況是因為最后一個必然是H或者D，而此時可以考慮把新加的一個放在最后，因為假如加的是H，如果加在[i-1][j]中加入H，則最后一個依然是H或D，此時如果成立，那么依然屬于[i-1][j]或[i][j-1]的情況。

所以推導出此遞推關系。

#include <iostream>

using namespace std;

int main()
{
??? __int64 d[21][21];
??? d[1][1] = 1;
??? d[2][1] = 2;
??? d[1][2] = 0;
??? for(int i = 1; i<21;i++)
??????? d[i][1] = i;
??? for(int i = 2;i<21;i++)
??? for(int j = 2;j<21;j++)
??? {
??????? if(i>=j)
??????? d[i][j] = d[i-1][j] + d[i][j-1];
??????? else d[i][j] = 0;
??? }
??? int m,n;
??? while(cin>>m>>n)
??? cout<<d[m][n]<<endl;
??? return 0;
}

總結

以上是生活随笔為你收集整理的HDU 下沙的沙子有几粒的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。