首页 > 代码库 > C语言 · 拿糖果

C语言 · 拿糖果

2024-09-07 03:21:17   208人阅读

算法提高 拿糖果  
时间限制：1.0s   内存限制：256.0MB
    
问题描述
　　妈妈给小B买了N块糖！但是她不允许小B直接吃掉。
　　假设当前有M块糖，小B每次可以拿P块糖，其中P是M的一个不大于根号下M的质因数。这时，妈妈就会在小B拿了P块糖以后再从糖堆里拿走P块糖。然后小B就可以接着拿糖。
　　现在小B希望知道最多可以拿多少糖。
输入格式
　　一个整数N
输出格式
　　最多可以拿多少糖
样例输入
15
样例输出
6
数据规模和约定
　　N <= 100000
 
作者注释：
1、题目易懂。
2、学会一招：#define max(a,b) (a>b)?a:b——若在之前学会，会省多少时间了。
 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<math.h>
 4 #define max(a,b) (a>b)?a:b
 5 int prime[110], vis[350], dp[100010];
 6 main(){
 7     int n, cur, i, j, k;  
 8     scanf("%d", &n);  
 9     cur=0;  
10     memset(vis, 0, sizeof(vis));  
11     for(i=2; i<350; i++){  
12         if(!vis[i]){  
13             prime[cur++]=i;
14             for(j=i+i; j<350; j=j+i){  
15                 vis[j]=1;  
16             }     
17         }  
18     }  
19     memset(dp, 0, sizeof(dp));  
20     for(i=1; i<=n; i++){  
21         for(j=0; j<=cur-1; j++){  
22             if(prime[j]<=sqrt(i)){
23                 if(i%prime[j]==0)  
24                 dp[i]=max(dp[i],dp[i-2*prime[j]]+prime[j]);//拿多的 
25             }  
26             else{  
27                 break;  
28             }  
29         }  
30     }  
31     printf("%d",dp[n]);  
32 }

 

 

C语言 · 拿糖果


联系
我们