程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> poj 3014 Cake Pieces and Plates 整數拆分

poj 3014 Cake Pieces and Plates 整數拆分

編輯:C++入門知識

poj 3014 Cake Pieces and Plates 整數拆分


題意:

將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 
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;	
} 


 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved