squanchy

用户名：uq_11086648109

访问量：1405

签　名：

等　　级
排　　名	17889
经　　验	761
参赛次数	0
文章发表	2
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

基于动态规划思路的拿糖果解题方案
浏览：705

你可能喜欢

C语言程序设计教程（第三版）课后习题6.8 （Java代码）

The 3n + 1 problem （C++代码）（所有测试数据都小于等于1000，，说好的1000000之内呢）

优质题解

基于动态规划思路的拿糖果解题方案

　　作者: squanchy　　　　发表时间：2020-02-24 21:53:44 浏览：705　|　评论：0　

原题链接：蓝桥杯算法提高VIP-拿糖果

思路:
1.当M个糖果减去2q个变成M-2q个就转换了状态，这是典型的动态规划思想,dp[M]=max(q+dp[M-2q])
2.考虑到N<=100000，数据规模较大，因此要尽量减少循环次数，决定提前算出质数，到时候再进行M%prime[j]==0的判断和prime[j]<=sqrt(M)的判断。
启发:
1.应用动态规划解题需要有这样的思维链:用几维数组，数组的每个单元代表什么,单元间怎么状态转移，数组要怎么初始化。
代码:
```cpp
#include<iostream>
#include<vector>
#include<string.h>
#include <algorithm>
#include<math.h>
using namespace std;
vector<int> prime;
void get_prime(int n)//求<=sqrt(n)的n的质因数，放在prime里
{
	int n_sqrt = sqrt(n);
	prime.push_back(2);
	for (int i = 2; i <= n_sqrt; i++)
	{
		int i_sqrt = sqrt(i);
		bool add = true;
		for (int j = 2; j <= i_sqrt + 1; j++)
		{
			if (i % j == 0)
			{
				add = false;
				break;
			}
		}
		if (add)
			prime.push_back(i);//符合条件的数字加入prime
	}
}
int main()
{
	int n, * dp;
	cin >> n;
	dp = new int[n + 1];
	get_prime(n);
	int length = prime.size();
	dp[0] = 0;//初始化要想清楚
	for (int i = 1; i <= n; i++)//从1开始计算dp[i]
	{
		int i_sqrt = sqrt(i);//为减小运算规模，将开方运算放在外层
		int max = 0;
		for (int j = 0; j <= length - 1 && prime[j] <= i_sqrt && i - 2 * prime[j] >= 0; j++)
		{
			if (i % prime[j] == 0)
			{
				if (max < prime[j] + dp[i - 2 * prime[j]])
					max = prime[j] + dp[i - 2 * prime[j]];//状态转换方程要想清楚
			}
		}
		dp[i] = max;//dp[i]=最大(q+dp[i-2*q])
	}
		cout <<dp[n];
	return 0;
}
```

0.0分

2 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

squanchy

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

C语言程序设计教程（第三版）课后习题6.8 （Java代码）

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

C语言考试练习题_保留字母（C语言代码）

The 3n + 1 problem （C++代码）（所有测试数据都小于等于1000，，说好的1000000之内呢）

基于动态规划思路的拿糖果解题方案

评论区

精彩推荐

C二级辅导-求偶数和（C语言代码）

C语言训练-求素数问题（C语言代码）

C二级辅导-进制转换（C语言代码）

C语言考试练习题_排列（C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

母牛的故事（C语言代码）

squanchy

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

C语言程序设计教程（第三版）课后习题6.8 （Java代码）

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

C语言考试练习题_保留字母 （C语言代码）

The 3n + 1 problem （C++代码）（所有测试数据都小于等于1000，，说好的1000000之内呢）

基于动态规划思路的拿糖果解题方案

评论区

精彩推荐

C二级辅导-求偶数和 （C语言代码）

C语言训练-求素数问题 （C语言代码）

C二级辅导-进制转换 （C语言代码）

C语言考试练习题_排列 （C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

母牛的故事 （C语言代码）

C语言考试练习题_保留字母（C语言代码）

　　评论区

C二级辅导-求偶数和（C语言代码）

C语言训练-求素数问题（C语言代码）

C二级辅导-进制转换（C语言代码）

C语言考试练习题_排列（C语言代码）

母牛的故事（C语言代码）