最大和---记忆化搜索

路径类问题--

1.变量--当前路径

2.边界条件-->n return 0

                ==n return dp[n]=a[n]

               记忆化！=inf return dp[i]

3.转移，dp【i】就是要记录最大值a【i】+s

同时s不能取0，因为会有负数

蓝桥账户中心

创作中心-CSDN

#include<bits/stdc++.h>
using namespace std;
#define N 100011
typedef  long long ll;
int n;
int a[N]; 
ll dp[N];
int d(int x)
{if(x==1) return 1;for(int i=2;i<=sqrt(x);i++){if(x%i==0) return i;}return x;
}
ll ma;
ll dfs(int x)
{if(x==n) return a[n];if(x>n) return 0;///大于n没有a就是0 if(dp[x]!=0x3f3f3f3f3f3f3f3fLL) return dp[x];///记忆化 ll s=-1*0x3f3f3f3f3f3f3f3fLL;for(int i=x+1;i<=x+d(n-x);i++){dp[i]=dfs(i);s=max(s,dp[i]);///s选最大的dp，也就是跳最大的 }dp[x]=a[x];///跳到这里起码有个a[x] dp[x]+=s;return dp[x];
}
int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n;for(int i=1;i<=n;i++) cin>>a[i];memset(dp,0x3f,sizeof(dp));dfs(1);cout<<dp[1];return 0;
}