当前位置: 代码迷 >> 综合 >> poj 3014 Cake Pieces and Plates 整数拆分
  详细解决方案

poj 3014 Cake Pieces and Plates 整数拆分

热度:21   发布时间:2024-01-19 05:47:46.0

题意:

将m拆成n个数,允许某个数为0,求拆分方案数。

分析:

裸的整数拆分,设h(m,n)表示将m拆成n个数,允许某数为0的方案数,递推方程见代码。很有意思的是,参考上一篇写poj1221的博文中,设f(m,n)表示将m进行任意份数不允许有0的整数拆分,且最大元素小于等于m的方案数,则h(m,n)==f(m,n)。。。。求解此等式意义。。。

代码:

//poj 3014
//sep9
#include <iostream>
using namespace std;
const int maxN=4500;
const int mod=1000000007;int a[maxN+10][maxN+10];
int main()
{int m,n;scanf("%d%d",&n,&m);for(int i=1;i<=m;++i)for(int j=1;j<=n;++j){if(i==1||j==1)a[i][j]=1;else if(j>i)a[i][j]=a[i][i];	else if(j==i)a[i][j]=a[i][j-1]+1;else{a[i][j]=(a[i][j-1]+a[i-j][j]);if(a[i][j]>=mod)a[i][j]-=mod;}}printf("%d\n",a[m][n]%mod);return 0;	
}