首页 > 代码库 > hdu 1267 下沙的沙子有几粒？(二维递推题)
hdu 1267 下沙的沙子有几粒？(二维递推题)
hdu 1267 下沙的沙子有几粒？(二维递推题)
题意：就是给你m个H和n个D，然后从左开始数H的累积个数总是不比D的累计数少的排列有多少种举一个测试案例吧：3个H和1个D总共有3种排列，依次是：H D H H,H H D H,H H H D三种排列，亲~意思应该懂了吧？！呵呵。。。
思路：递推公式为：a[m][n]=a[m-1][n]+a[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种方案（其它的添加方法都是重复的，不信的话自己可以试一下）
1 #include <stdio.h> 2 #include <string.h> 3 4 int main() 5 { 6 int n,m; 7 __int64 a[25][25]; //注意这种用法，虽然说相当于longlong，但换成longlong后就会WA...囧（前面有两条短横线） 8 int i,j; 9 memset(a,0,sizeof(a));10 for(i = 0; i<=20; i++)11 {12 a[i][0] = 1;13 }14 for(i = 1; i<=20; i++)15 {16 for(j = 1; j<=20; j++)17 {18 if(i<j)19 break;20 a[i][j] = a[i-1][j] + a[i][j-1];21 }22 }23 while(~scanf("%d%d",&n,&m))24 {25 printf("%I64d\n",a[n][m]); //这种输出方式....26 }27 28 return 0;29 }
这种题现在的我还hold不住，递推公式给不出来就不会写.....T_T
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。