hdu-1267 下沙的沙子有几粒 DP/Catalan

纠结 的题啊

ACMStep的2.3.8

在2.3里一看题就往Catalan数上想了 很欣喜的推导出了公式：C[m][n]=(m-n+1)/n*C[m][n-1];C[m][0]=1;其中，m是D可以放置的位置数。

最后用大数的处理方式计算出了结果 提交后WA嗄 愣是想了半天不知道为何嗄

最后的最后 找了himdd的博文，发现可以用DP的思想。

解法一：DP

代码及解析如下：

#include<iostream>
using namespace std;
long long num[23][23];
int Calculate()
{
int i,j;
num[0][0]=1;
//神奇的DP
for(i=1;i<22;i++)
{
num[i][0]=1;
for(j=1;j<=i;j++)
num[i][j]=num[i-1][j]+num[i][j-1];
//i个H和j个D可以看成是：
//i-1个H和j个D的串串最后补一个H
//i个H和j-1个D的串串最后补一个D
}
return 0;
}
int main()
{
Calculate();
int m,n;
while(cin>>m>>n)
{
cout<<num[m][n]<<endl;
}
return 0;
}

解法二：

Catalan思想：

C(n,m)=C(m+n,m)-C(m+n,m+1);（一般的Catalan是n与2n的关系，此题为n+m的关系）

代码 l略

附上俺的Catalan想法及代码：

对于m个H，n个D。可以先把H的位置固定，其中对于第一个H后可以放置1个D，第i个放置i个D，当i>n时，可放置n个D。一共num个位置可放置D。

在num个位置中选择n个即为串串的个数。

（尚未想通为什么不对呢）

#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
//公式：C[m][n]=(m-n+1)/n*C[m][n-1];
C[m][0]=1;
int C[211][21][101];
int Calculate()
{
int i,j,k;
for(i=1;i<=210;i++)
{
C[i][0][0]=1;
int len=1;
//乘(m-n+1)
for(j=1;j<=i&&j<=20;j++)
{
int flag=0;
for(k=0;k<len;k++)
{
int w=(i-j+1)*C[i][j-1][k]+flag;
C[i][j][k]=w%10;
flag=w/10;
}
while(flag)
{
C[i][j][k++]=flag%10;
flag/=10;
}
len=k;
//除n
while(k>=0)
{
int y=C[i][j][k]+flag*10;
C[i][j][k]=y/j;
flag=y%j;
k--;
}
}
}
return 0;
}
int main()
{
memset(C,0,sizeof(C));
Calculate();
int m,n;
int i,j;
int num=0;
while(cin>>m>>n)
{
num=0;
for(i=1;i<=m;i++)//计算字符D可以放置的位置
{
if(i<n)
num+=i;
else num+=n;
}
cout<<num<<endl;
j=100;
while (C[num][n][j]==0)
{
j--;
}
while(j>=0)
cout<<C[num][n][j--];
cout<<endl;
}
return 0;
}

最后

以上就是矮小夕阳为你收集整理的hdu-1267 下沙的沙子有几粒 DP/Catalan的全部内容，希望文章能够帮你解决hdu-1267 下沙的沙子有几粒 DP/Catalan所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。