蓝桥杯刷题打卡

#include <iostream>
using namespace std;
int find(int x){//求质因数，纯暴力。
  for(int i = 2;i <= x/2; i++){
    if(x%i==0){
      for(int j = 2;j <= i; j++){
        if(j==i){
          return j;
        }
        if(i%j==0){
          break;
        }
      }
    }
  }
  return x;
}
int price(int nums[10000],int D[10000],int n){//dp，最后dp[n-1]为最终值
  int dp[10000];
  dp[0] = nums[0];
  for(int i = 1;i < n; i++){
    dp[i] = dp[i-1] + nums[i];
    for(int j = i-1;j >= 0; j--){
      if(i-j<=D[j]){
        if(dp[j]+nums[i]>dp[i]){//更新，dp数组的建立就是存储每一步的最大价值。
          dp[i] = dp[j] + nums[i];
        }
      }
    }
  }
  return dp[n-1];//返回
}
int main()
{
  // 请在此输入您的代码
  int n;
  int nums[10000];
  int D[10000];//记录脚力
  cin>>n;
  for(int i = 0;i < n; i++){
    cin>>nums[i];
    D[i] = find(n-i-1);//脚力
  }
  int k = price(nums,D,n);//直接输出就行了，int k多余了。
  cout<<k;
  return 0;
}