HDU1028 Ignatius and the Princess III(整数拆分：母函数||DP)

本文主要是介绍HDU1028 Ignatius and the Princess III(整数拆分：母函数||DP)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：

给出一个值n，问有几种不同的拆分方法。

要点：

可以用母函数或DP来做，这里说一下母函数，基本思路是：写成(1+x^2+x^3+x^4……x^n)*(1+x^2+x^4+……)*(1+x^3+x^6+……)……这样，然后利用循环从每个括号开始算起，用c1存储前一次算出的所有指数对应的系数，c2暂存算上当前括号的对应系数，最后c1[n]就是答案。

母函数：

#include<iostream>
#include<algorithm>
using namespace std;int main()
{int n,i,j,k;while(scanf("%d",&n)!=EOF){int c1[125],c2[125];for(i=0;i<=n;i++)//一开始所有指数的系数都是1 {c1[i]=1;//c1表示未算当前括号内的前面元素的系数 c2[i]=0;//c2表示算上当前括号的总和，是个暂存的数组 }for(i=2;i<=n;i++)//从第2个括号开始算起，第一个都是1不用算 {for(j=0;j<=n;j++)//计算所有指数 {for(k=0;k+j<=n;k+=i)//第i个括号中每个元素与前面已经算出的元素相乘，指数变化 {c2[k+j]+=c1[j];}}for(j=0;j<=n;j++)//系数保存在前一个数组内 {c1[j]=c2[j];c2[j]=0;}}printf("%d\n",c1[n]);		}return 0;
}

#include<iostream>
#include<cstdlib>
#include<cstring> 
#include<algorithm>
using namespace std;
int dp[125][125];//dp[i][j]表示i被拆分为最大因数为j的方法数int cal(int n,int m)
{if(dp[n][m]!=-1)return dp[n][m];if(n<1||m<1) return dp[n][m]=0;if(n==1&&m==1)return dp[n][m]=1;if(n<m)return dp[n][m]=cal(n,n);if(n==m)return dp[n][m]=cal(n,m-1)+1;//自己整个作为一种 return dp[n][m]=cal(n,m-1)+cal(n-m,m);//有两种情况，使用m或不使用m 
} int main()
{int n;while(~scanf("%d",&n)){memset(dp,-1,sizeof(dp));printf("%d\n",cal(n,n));} return 0;
}

这篇关于HDU1028 Ignatius and the Princess III(整数拆分：母函数||DP)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！