HDU 下沙的沙子有几粒

2017-11-15 23:50:00

分析，这题其实是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;

}

本文转自NewPanderKing51CTO博客，原文链接：http://www.cnblogs.com/newpanderking/archive/2011/07/31/2122540.html ，如需转载请自行联系原作者

继续阅读