HDU ACM 1267 下沙的沙子有几粒?->DP

题意:m个H和n个D,从左開始数H的累积个数总不比D的累计数少的排列有多少种。比如,3个H和1个D共同拥有3种符合要求的排列H D H H,H H D H,H H  H D。
分析:状态方程为,DP[m][n]=DP[m-1][n]+DP[m][n-1]。

另外当n=0的时候不管m怎样取值都是1。

理解:如果3个H和2个D是由2个H和2个D还有3个H一个D推来的,2个H和2个D共同拥有H D H D。H H D D两种排列,3个H和一个D总共同拥有H D H H,H H D H,H H  H D三种排列,然后在H D H D,H H D D的后面加入一个H就是2中排列,在H D H H,H H D H,H H  H D的后面加入一个D就有3种方案,所以总共就是5种方案。其它均为反复。

注意:m<n的话排列的情况不存在,则为0。

#include<iostream>   
using namespace std;

int main()  
{
	__int64 a[21][21];
	int m,n,i,j;

	memset(a,0,sizeof(a));
	for(i=1;i<=20;i++) //当n为0的时候不管m怎样取何值都是1
		a[i][0]=1;

	for(i=1;i<=20;i++)
		for(j=i;j<=20;j++)
			a[j][i]=a[j-1][i]+a[j][i-1];

	while(cin>>m>>n)
	{
		printf("%I64d
",a[m][n]);
	}
    return 0;  
}


原文地址:https://www.cnblogs.com/mengfanrong/p/5095894.html