首页 > 代码库 > poj 1664 放平果
poj 1664 放平果
此问题可分为两个子问题:当m<n时,如3个苹果放入4个盘子中,和3个苹果放3个盘子的方法数是一样的。
所以m<n时,f[m][n]=f[m][m];
当m>=n时,可分为两种放法,一种为至少有一个盘子为空,则有f[m][n-1]种放法。
另外为n个盘子都不为空,则先将n个苹果一个一个放入n的盘子中,剩下的m-n个苹果再放入n个盘子中。此放法就相当于m-n个苹果放n个盘子里面,有f[m-n][n]种放法。
所以状态转移方程为f[i][j]:if(i>=j)f[i][j]=f[i][j-1]+f[i-j][j]
if(i<j) f[i][j]=f[i][i];
相当于整数的拆解
#include<stdio.h> int num(int m,int n) { if(m<0) return 0; if(m==0||n==1) return 1; return num(m,n-1)+num(m-n,n); } int main() { int n,m,t; scanf("%d",&t); while(t--) { scanf("%d%d",&m,&n); printf("%d\n",num(m,n)); } return 0; }
poj 1664 放平果
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。