hdu 1267 下沙的沙子有几粒？

96 阅读 0 评论 64 点赞

我是靠谱客的博主单身老虎，最近开发中收集的这篇文章主要介绍hdu 1267 下沙的沙子有几粒？，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

hdu 1267 下沙的沙子有几粒？题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1267

题目分析：可以算是DP么？说是递推还差不多，不难。dp[i][j]表示有i个H和j个D时的解，只需要考虑当前是加了一个H还是D，如果是D，那么种数就是a[i][j-1]，H的话就是a[i-1][j]。那么状态转移方程就是dp[i[j]=dp[i-1][j]+dp[i][j-1]。

code:

#include<stdio.h>
__int64 dp[30][30];//i个H,j个D
int main()
{
int m,n,i,j;
for(i=1;i<=20;i++)
{
dp[i][1]=i;
dp[1][i+1]=0;
}
for(i=2;i<=20;i++)
{
for(j=2;j<=i;j++)
{
dp[i][j]=dp[i-1][j]+dp[i][j-1];
}
}
while(scanf("%d%d",&n,&m)!=EOF)
{
printf("%I64dn",dp[n][m]);
}
return 0;
}

PS：苦逼的A step王者之路啊，又往前走了一步，赶紧到DP吧……