蓝桥杯练习：算法提高拿糖果

一时失言乱红尘 2022-09-28 16:17 225阅读 0赞

问题描述

妈妈给小B买了N块糖！但是她不允许小B直接吃掉。  
　　假设当前有M块糖，小B每次可以拿P块糖，其中P是M的一个不大于根号下M的质因数。这时，妈妈就会在小B拿了P块糖以后再从糖堆里拿走P块糖。然后小B就可以接着拿糖。  
　　现在小B希望知道最多可以拿多少糖。

输入格式

一个整数N

输出格式

最多可以拿多少糖

样例输入

15

样例输出

6

数据规模和约定

N <= 100000

package lanqiao;
    
    import java.util.Scanner;
    
    
    public class Main
    {
    	static int prime[]=new int[50000];  
    	static int dp[]=new int[100005];  
    	static int book[]=new int[100005];  
    	static int cnt = 0; 
    	public static void create() {  
    	    int len = (int) Math.sqrt(100005);  
    	    for(int i = 2; i <= len; i++) {  
    	        if(book[i] == 0) {  
    	            prime[cnt++] = i;  
    	            for(int j = i * i; j <= len; j = j + i)  
    	                book[j] = 1;  
    	        }  
    	    }  
    	} 
    	public static void main(String[] args)
    	{
    		Scanner scanner=new Scanner(System.in);
    		
    		
    		  create();  
    		    int n;  
    		    n=scanner.nextInt();
    		    for(int i = 1; i <= n; i++) {  
    		        for(int j = 0; j < cnt; j++) {  
    		            if(prime[j] > Math.sqrt(i))  
    		                break;  
    		            if(i % prime[j] == 0)  
    		                dp[i] = Math.max(dp[i], dp[i-2*prime[j]] + prime[j]);  
    		        }  
    		    }  
    		   
    		    System.out.println(dp[n]);
    		
    	}
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，225人围观）

还没有评论，来说两句吧...

相关阅读

相关蓝桥杯算法提高合并石子（dp）

算法提高合并石子时间限制：2.0s 内存限制：256.0MB 问题描述　　在一条直线上有n堆石子，每堆有一定的数量，每次可以将两堆相邻的石子合并，合并后放在两堆的中

超、凢脫俗/ 2024年02月17日 19:43/ 0 赞/ 36 阅读

相关蓝桥杯历届试题分糖果

历届试题分糖果时间限制：1.0s 内存限制：256.0MB 问题描述　　有n个小朋友围坐成一圈。老师给每个小朋友随机发偶数个糖果，然后进行下面的游戏：　

快来打我*/ 2024年02月17日 19:38/ 0 赞/ 66 阅读

相关【蓝桥杯java算法提高】整商问题

【问题描述】　　提示用户输入被除数（dividend）和除数（divisor），若除数为0，则提示用户重新输入，直至除数非零为止。最后输出商。程序建议大家将被除数、除数和

快来打我*/ 2022年12月13日 01:24/ 0 赞/ 160 阅读

相关蓝桥杯练习：算法提高拿糖果

问题描述　　妈妈给小B买了N块糖！但是她不允许小B直接吃掉。　　假设当前有M块糖，小B每次可以拿P块糖，其中P是M的一个不大于根号下M的质因数。这时，妈妈就会在小B拿

一时失言乱红尘/ 2022年09月28日 16:17/ 0 赞/ 226 阅读

相关蓝桥杯练习：算法提高 9-2 文本加密

问题描述　　先编写函数EncryptChar,按照下述规则将给定的字符c转化（加密）为新的字符："A"转化"B"，"B"转化为"C"，... ..."Z"转化为"a"，"a

r囧r小猫/ 2022年09月28日 15:30/ 0 赞/ 135 阅读

相关蓝桥杯练习：算法提高队列操作

问题描述　　队列操作题。根据输入的操作命令，操作队列（1）入队、（2）出队并输出、（3）计算队中元素个数并输出。输入格式　　第一行一个数字N。　　下面N行，

野性酷女/ 2022年09月28日 05:53/ 0 赞/ 171 阅读

相关蓝桥杯算法提高拿糖果

![这里写图片描述][SouthEast] import java.util.Scanner; public class Main {

旧城等待，/ 2022年06月02日 11:42/ 0 赞/ 209 阅读

相关蓝桥杯分糖果

问题描述　　有n个小朋友围坐成一圈。老师给每个小朋友随机发偶数个糖果，然后进行下面的游戏：　　每个小朋友都把自己的糖果分一半给左手边的孩子

「爱情、让人受尽委屈。」/ 2022年03月06日 05:56/ 0 赞/ 246 阅读

相关蓝桥杯试题算法提高递归输出

试题算法提高递归输出资源限制时间限制：1.0s 内存限制：512.0MB 问题描述　　编写递归函数，将组成整数的所有数字逐个输出，每个数字后面加上一个减

短命女/ 2021年09月24日 00:28/ 0 赞/ 275 阅读

相关蓝桥杯试题算法提高特等奖学金

试题算法提高特等奖学金资源限制时间限制：1.0s 内存限制：256.0MB 问题描述　　土豪大学每年都会给学生颁发巨额的特等奖学金，当然，获奖的前提是要

亦凉/ 2021年09月24日 00:26/ 0 赞/ 365 阅读