【线性筛+DP】最大和

系统管理员 2024-03-26 16:51 74阅读 0赞

看错题了，呃呃，其实就是个简单DP

[最大和 - 蓝桥云课 (lanqiao.cn)][- _ _lanqiao.cn]

题意：

![1c1959b04b6355319348ec8acf035e3b.png][]

思路：

设dp\[i\]为以1为终点的最大和，然后枚举状态和决策就行了

主要是线性筛的应用，它可以预处理出一个数的最小质因子是多少

Code：

#include <bits/stdc++.h>
    using namespace std;
    const int mxn=1e4+10;
    int n,len=0;
    int a[mxn],dp[mxn];
    int prime[mxn],vis[mxn],d[mxn];
    void p_init(){
        d[1]=1;
        for(int i=2;i<=n;i++){
            if(!vis[i]) prime[++len]=i,d[i]=i;
            for(int j=1;i<=n/prime[j];j++){
                vis[i*prime[j]]=1;
                d[i*prime[j]]=prime[j];
                if(i%prime[j]==0) break;
            }
        }
    }
    void solve(){
        cin>>n;
        p_init();
        for(int i=1;i<=n;i++) cin>>a[i];
        memset(dp,-0x3f,sizeof(dp));
        dp[1]=a[1];
        for(int i=1;i<=n;i++){
            for(int j=i+1;j<=min(i+d[n-i],n);j++){
                dp[j]=max(dp[j],dp[i]+a[j]);
            }
        }
        cout<<dp[n]<<'\n';
    }
    int main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[- _ _lanqiao.cn]: https://www.lanqiao.cn/problems/2385/learning/?contest_id=80
[1c1959b04b6355319348ec8acf035e3b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/69f069de3740482a9e20bac5cd9fdc40.png

发表评论取消回复

表情：

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

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

相关阅读

相关【线性筛】阶乘约数

看老师写的DP看了一万年终于有点会了题意： ![597c1378397f2be58a7114e70521a2f6.png][] 思路：先去跑线性筛，把一个数的最

你的名字/ 2024年03月26日 18:30/ 0 赞/ 80 阅读

相关【线性筛+DP】最大和

看错题了，呃呃，其实就是个简单DP [最大和 - 蓝桥云课 (lanqiao.cn)][- _ _lanqiao.cn] 题意： ![1c1959b04b63553193

系统管理员/ 2024年03月26日 16:51/ 0 赞/ 75 阅读

相关 Kuangbin 线性DP 最大和加强加强版

呃呃，一道题写了我一下午 [4546. 最大和加强加强版 - AcWing题库][4546. _ - AcWing] 题意： ![ba4b2758a59b89b0eeb4

ゝ一世哀愁。/ 2024年03月26日 16:06/ 0 赞/ 99 阅读

相关【线性筛】漂亮数

[1006-漂亮数\_2021秋季算法入门班第十章习题：数学 (nowcoder.com)][1006-_2021_ _nowcoder.com] 题意： ![28c4c1

今天药忘吃喽~/ 2024年03月24日 08:08/ 0 赞/ 17 阅读

相关质数 AcWing 868. 筛质数线性筛

质数 AcWing 868. 筛质数原题链接 [AcWing 868. 筛质数][AcWing 868.] 算法标签数学知识质数线性筛法筛法求素数

水深无声/ 2023年09月28日 11:35/ 0 赞/ 30 阅读

相关【素数判断】埃氏筛法和欧拉筛法（线性筛法）

埃氏筛法埃氏筛法的原理是：给出要筛数值的范围n，找出以内的素数。先用2去筛，即把2留下，把2的倍数剔除掉；再用下一个质数，也就是3筛，把3留下，把3的倍数剔

本是古典何须时尚/ 2023年01月10日 10:28/ 0 赞/ 161 阅读

相关 dp之最大和，m段最大和以及最大子矩阵

前一段时间因为要讲课学习了dp系列算法，学习了很多东西，给大一菜鸟讲了这个系列的算法，当时没有记录，前几天拿起来发现有点忘记了，所以在这里记录一下，最大和系列算法。首先子串

系统管理员/ 2022年09月20日 09:26/ 0 赞/ 156 阅读

相关 dp学习——最大字段和

输入第1行：整数序列的长度N（2 <= N <= 50000) 第2 - N + 1行：N个整数（-10^9 <= A\[i\] <= 10^9）输出输出最大子

喜欢ヅ旅行/ 2022年08月21日 00:18/ 0 赞/ 169 阅读

相关素数线性筛模板

[参考于该博客][Link 1] int Mark[MAXSIZE]; int prime[MAXSIZE]; //判断是

╰+哭是因爲堅強的太久メ/ 2022年05月14日 03:36/ 0 赞/ 256 阅读

相关 [* dp]53. 最大子序和

给定一个整数数组 `nums` ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。暴力解决时间复杂度太高，用动态规划：设sum\[i\]为

拼搏现实的明天。/ 2021年12月05日 17:45/ 0 赞/ 239 阅读