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

poj 1221 UNIMODAL PALINDROMIC DECOMPOSITIONS 整數拆分

編輯:C++入門知識

poj 1221 UNIMODAL PALINDROMIC DECOMPOSITIONS 整數拆分


題意:

給一個數n,求有多少種和為n的單峰先增對稱序列,比如當n=5時結果為3:(5), (1 3 1), (1 1 1 1 1)。

分析:

轉化為求類似整數拆分問題,f(i,j)的意義是把i進行拆分,最大數小於等於j的方法數。

代碼:

 

//poj 1221
//sep9
#include 
using namespace std;
const int maxN=300;
__int64 a[maxN+10][maxN+10];


__int64 f(int m,int n)
{
	if(a[m][n]!=-1)
		return a[m][n];
	if(m==1||n==1)
		return a[m][n]=1;
	if(n>m)
		return a[m][n]=f(m,m);
	else if(n==m)
		return a[m][n]=f(m,n-1)+1;
	else
		return a[m][n]=f(m,n-1)+f(m-n,n);
}

int main()
{
	memset(a,-1,sizeof(a));
	int n;
	while(scanf("%d",&n)==1&&n){
		__int64 sum=1;
		for(int mid=1;mid

 

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