ADV-205 拿糖果

ADV-205 拿糖果
问题描述
妈妈给小B买了N块糖!但是她不允许小B直接吃掉。
假设当前有M块糖,小B每次可以拿P块糖,其中P是M的一个不大于根号下M的质因数。这时,妈妈就会在小B拿了P块糖以后再从糖堆里拿走P块糖。然后小B就可以接着拿糖。
现在小B希望知道最多可以拿多少糖。
输入格式
一个整数N
输出格式
最多可以拿多少糖
样例输入
15
样例输出
6
数据规模和约定
N <= 100000

[思路]:

动态规划的思想,设已经拿了n块糖,则最终最多可以拿的糖取决于从剩下的M块糖里,最多可以拿多少糖,则有

solve(M,n)=n+MAX(M)

而MAX(M)=max{solve((M-2*P1)+P1),solve((M-2*P2)+P2),solve((M-2*P3)+P3)….}

所以有solve(M,n)=n+max{solve((M-2*P1)+P1),solve((M-2*P2)+P2),solve((M-2*P3)+P3)….}

求MAX(M)的过程可以在循环中做,最后将MAX(M)的保存在数组里,优化递归,减少运算。

代码:

#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int maxn=100000+10;
int MAX[maxn];
int is_zhishu(int n){
	for(int i=2;i<=sqrt(n);i++)
		if(n%2==0) return 0;
	return 1;
}
int solve(int M,int n){
	if(MAX[M]>=0) return MAX[M]+n;
	int t=0,max=0;
		for(int i=2;i<=sqrt(M);i++){//循环求MAX[M] 
			if(M%i==0&&is_zhishu(i))
			   t=solve(M-i*2,i);
			   if(max<t) max=t; 
	} 
	return (MAX[M]=max)+n;	
} 
int main(){
    int N;	
	scanf("%d",&N);
	memset(MAX,-1,sizeof(MAX));
	MAX[0]=0,MAX[1]=0,MAX[2]=0,MAX[3]=0;
	printf("%d\n",solve(N,0));
	return 0;
} 
2016年5月13日 | 归档于 蓝桥杯
标签:
本文的评论功能被关闭了.