XMU 1255_TinyMind

http://acm.xmu.edu.cn/JudgeOnline/problem.php?id=1255

整数划分问题 996ms险过..（递归法）

#include<cstdio>
#include<string>
#include<map>
using namespace std;
int n,mod;
long long dps[500][500];
long long dp(int n,int m){      //n表示要拆分的整数，m表示拆成的数最大是几/拆成m个数的和
	if(n<=1 || m==1)return 1;
	if(n<m)return dp(n,n);
	if(dps[n][m])return dps[n][m];
	return dps[n][m]=(dp(n,m-1)+dp(n-m,m));
}
int main(){
	long long sum;
	for(int i=1;i<=400;i++)
		dps[i][i]=dp(i,i);
	while(scanf("%d %d",&n,&mod)!=EOF){
		sum=0;
		for(int i=1;i<=n;i++)
			sum=(sum+dps[i][i])%mod;
		printf("%lld\n",sum);
	}
}

（母函数法）也是896ms险过..

#include<stdio.h>
#include<string>
using namespace std;
int n,mod;
long long c1[500],c2[500];
int main(){
	int i,j,k;
	memset(c2,0,sizeof(c2));
	for(i=0;i<=400;i++)
		c1[i]=1;
	for(i=2;i<=400;i++){
		for(j=0;j<=400;j++)
			for(k=0;k+j<=400;k+=i)
				c2[k+j]=(c2[k+j]+c1[j]);
		for(j=0;j<=400;j++){
			c1[j]=c2[j];
			c2[j]=0;
		}
	}
	while(scanf("%d %d",&n,&mod)!=EOF){
		long long sum=0;
		for(i=1;i<=n;i++)
			sum=(sum+c1[i])%mod;
		printf("%lld\n",sum);
	}
}

优质内容筛选与推荐>>
1、面试算法题
2、项目管理整体图
3、SQL函数学习（四）：charindex()函数
4、调研《构建之法》指导下的各类全国性大学生信息化相关的竞赛平台的优秀作品
5、XSS攻击及防御

朋友将在看一看看到

分享想法到看一看