列公子

用户名：lielielie

访问量：10578

签　名：

等　　级
排　　名	1691
经　　验	2704
参赛次数	0
文章发表	20
年　　龄	0
在职情况	学生
学　　校	哈尔滨工程大学
专　　业

　　自我简介：

TA的其他文章

蓝桥杯算法提高- 和最大子序列动态规划 C++
浏览：354

蓝桥杯算法提高VIP-种树动态规划 / DFS (C++)
浏览：944

蓝桥杯棋盘多项式 DFS (C++)
浏览：604

你可能喜欢

蓝桥杯算法提高- 拿糖果动态规划 (C++)

　　作者: 列公子　　　　发表时间：2020-02-17 19:36:43 浏览：444　|　评论：0　

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

# [1909] 拿糖果 动态规划法

## 1. 最优值的定义和递归关系
### 1.1 最优值定义
定义 $$dp[i]$$ 为初始有$$i$$个糖果的情况下, 能拿到的**最大糖果数**（即最优值）
### 1.2 最优值递归关系
$$dp[i] = max(dp[i - 2*j] + j ),  j \leq \sqrt {i}$$

同时 j 是 i 的**质因子**

## 2. 完整代码 (AC)
```cpp
// 蓝桥杯题库 1909 拿糖果
// 动态规划法
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
int prime[100005];      // 素数表
int len = 0;
bool isRemoved[100005];

int dp[100005];         // dp[i] 为初始 i 个糖果, 最多拿到的糖果数(最优值)
// dp[i] = max( dp[i], dp[i - prime[j]*2] + prime[j] ), prime[j] 是 i 不大于根号i 的质因子

void initPrime(){       // 筛法求素数表
    for (int i = 2; i < 100001; i++){
        if (!isRemoved[i]){
            prime[len++] = i;
            for (int j = i + i; j < 100001; j += i)
                isRemoved[j] = true;
        }
    }
}

int solve(int n){
    for (int i = 1; i <= n; i++){
        for (int j = 0; prime[j] <= sqrt(i) && j < len; j++){
            // 是质因子
            if (i % prime[j] == 0)
                dp[i] = max(dp[i], dp[i-prime[j] * 2] + prime[j]);
        }
    }
    return dp[n];
}

int main(){
    int N;
    scanf("%d", &N);
    initPrime();
    printf("%d", solve(N));
    return 0;
}

```

0.0分

2 人评分

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

列公子

TA的其他文章

你可能喜欢

字符逆序（C语言代码）

IP判断（C++代码）

简单的a+b （C语言代码）

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

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

蓝桥杯算法提高- 拿糖果动态规划 (C++)

评论区

精彩推荐

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

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

P1000 （C语言代码）

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

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

大家好，我是验题君

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

简单的a+b （C语言代码）

小O的乘积（C语言代码）

求圆的面积（C++代码）浮点数有误差！！！

列公子

TA的其他文章

你可能喜欢

字符逆序 （C语言代码）

IP判断 （C++代码）

简单的a+b （C语言代码）

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

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

蓝桥杯算法提高- 拿糖果 动态规划 (C++)

评论区

精彩推荐

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

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

P1000 （C语言代码）

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

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

大家好，我是验题君

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

简单的a+b （C语言代码）

小O的乘积 （C语言代码）

求圆的面积 （C++代码）浮点数有误差！！！

字符逆序（C语言代码）

IP判断（C++代码）

蓝桥杯算法提高- 拿糖果动态规划 (C++)

　　评论区

小O的乘积（C语言代码）

求圆的面积（C++代码）浮点数有误差！！！