HDU(1267)-下沙的沙子有几粒？

98 阅读 0 评论 65 点赞

我是靠谱客的博主自然小天鹅，最近开发中收集的这篇文章主要介绍HDU(1267)-下沙的沙子有几粒？，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

http://acm.hdu.edu.cn/showproblem.php?pid=1267

题目意思大致是：

假定一个字符串由m个H和n个D组成，从左到右扫描该串，如果字符H的累计数总是不小于字符D的累计数,那么，满足条件的字符串总数就恰好和下沙的沙粒一样多

也就是给你两个数m，n，让你求在满足上面条件的情况下，所求得的字符串有几种。

这道题是我自己第一次做dp，哈~ 而且也写出来了状态转移方程。

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

其实就是这样的，相当于01背包的思路一样，分成H取D不取或是H不取D取。然后化解为子问题来求解。

#include<stdio.h>
#include<string.h>
int main(){
int m,n,i,j;
__int64 dp[21][21]={0};
dp[0][1]=0; dp[1][0]=1;
for(i=1;i<21;i++)
dp[i][0]=1;
for(i=1;i<21;i++)
for(j=1;j<21;j++){
if(i>=j)
dp[i][j]=dp[i-1][j]+dp[i][j-1];
if(i<j)
dp[i][j]=0;
}
while(~scanf("%d%d",&m,&n)){
printf("%I64dn",dp[m][n]);
}
}