hdu1028(母函数+DP)
题目信息:求分解整数n的个数q(n);能够母函数或者DP
http://acm.hdu.edu.cn/showproblem.php?pid=1028
AC代码:
/******************************
题目大意:求分解整数n的个数q(n)
例:
5 = 5;
5 = 4 + 1;
5 = 3 + 1 + 1;
5 = 3 + 2;
5 = 2 + 2 + 1;
5 = 2 + 1 + 1 + 1;
5 = 1 + 1 + 1 + 1 + 1;
sum(5) = 7;不区分顺序,
(3+2)与(2+3)为同一个
*******************************/
/**
*DP
*/
#include<iostream>
using namespace std;
int a[121][121];//储存数组
long long q(int n,int m)
{//递归分析,m为分解的最大值
if((n<1)||(m<1)) return 0;
if((n==1)||(m==1)) return 1;
if(n<m) return q(n,n);
if(n==m) return q(n,m-1)+1;
return q(n,m-1)+q(n-m,m);
}
/**
int main()
{
for(int i=1;i<=120;i++){
for(int j=1;j<=120;j++){//由递归式转存到数组中。降低计算量
if((i==1)||(j==1)) a[i][j]=1;
else if(i<j) a[i][j]=a[i][i];
else if(i==j) a[i][j]=a[i][j-1]+1;
else a[i][j]=a[i][j-1]+a[i-j][j];
}
}
int n;
while(cin>>n){
cout<<a[n][n]<<endl;
}
return 0;
}**/
/**
*母函数解法
*/
int main()
{
int a[350],b[350],i,j,k,n;
while(cin>>n&&n)
{
for(i=0;i<=n;i++){
a[i]=1;
b[i]=0;
}
for(i=2;i<=n;i++){
for(j=0;j<=n;j++)
for(k=0;k+j<=n;k+=i)
b[k+j]+=a[j];
for(j=0;j<=n;j++){
a[j]=b[j];
b[j]=0;
}
}
cout<<a[n]<<endl;
}
return 0;
}
最新文章
- 数据存储单位的换算关系(TB、PB、EB、ZB、YB)
- osg矩阵变换节点-----平移旋转缩放
- vim - Removing duplicate lines
- 对于前端JS、Html、CSS的大小、位置是否影响网站的相应时间
- Luence学习笔记
- Oracle 12C RAC的optimizer_adaptive_features造成数据插入超时
- 路由器无线桥接 router wireless bridge
- P1896 [SCOI2005]互不侵犯King
- Qt计算器开发(二):信号槽实现数学表达式合法性检查
- 用appuploader生成发布证书和描述性文件
- Chapter 5 Blood Type——7
- AppBoxFuture(二): Say goodbye to sql!
- python之str字符串
- RobotFramework Selenium2 关键字
- 转:StarUML3.0的破解方法
- C++ Boost库简介(转载)
- dip和px的相互转化
- ssh密钥认证排错
- JSPatch 原理
- ionic--配置路由