【线性筛+DP】最大和

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

最大和 - 蓝桥云课 (lanqiao.cn)

题意：

思路：

设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;
}