問題描述

小藍在玩一個尋寶游戲，游戲在一條筆直的道路上進行，道路被分成了?n?個方格，依次編號 1 至?n，每個方格上都有一個寶物，寶物的分值是一個整數（包括正數、負數和零），當進入一個方格時即獲得了方格中寶物的分值。小藍可以獲得的總分值是他從方格中獲得的分值之和。

小藍開始時站在方格 1 上并獲得了方格 1 上寶物的分值，他要經過若干步 到達方格?n。

當小藍站在方格?p?上時，他可以選擇跳到?p+1?到?p+D(n?p)?這些方格 中的一個，其中?D(1)=1，D(x)(x>1)?定義為?x?的最小質因數。

給定每個方格中寶物的分值，請問小藍能獲得的最大總分值是多少。

輸入格式

輸入的第一行包含一個正整數?n。

第二行包含?n?個整數，依次表示每個方格中寶物的分值。

輸出格式

輸出一行包含一個整數，表示答案。

樣例輸入

5
1 -2 3 -1 5

樣例輸出

8

思路：

代碼：

記憶化搜索

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N], mem[N], primes[N], min_primes[N], cnt, n;
bool st[N];
void get_primes(int n) 
{for (int i = 2; i <= n; i++) {if (!st[i]) {primes[++cnt] = i;min_primes[i] = i; // 記錄質數的最小質因數是其本身}for (int j = 1; primes[j] <= n / i; j++) {st[primes[j] * i] = true;min_primes[primes[j] * i] = primes[j]; // 記錄合數的最小質因數if (i % primes[j] == 0) {break;}}}
}
// 計算 x 的最小質因數
int D(int x) 
{if (x == 1) return 1;if (min_primes[x])return min_primes[x];else {cout << " 該數沒有找到最小質因數 ：" << endl;return 1e9;}
}// 深度優先搜索并記憶化
int dfs(int x) 
{if (mem[x] != -1)return mem[x];if (x == n)return a[x];int sum = -1e9;for (int i = x + 1; i <= x + D(n - x) && i <= n ; i++) {sum = max(sum, dfs(i));}mem[x] = sum + a[x];return mem[x];
}int main() 
{cin >> n;get_primes(n);for (int i = 1; i <= n; i++) {cin >> a[i];}memset(mem, -1, sizeof(mem));cout << dfs(1);return 0;
}    

dp:
?

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N], dp[N], primes[N], cnt, n,min_primes[N];
bool st[N];
void get_primes(int n) 
{for (int i = 2; i <= n; i++) {if (!st[i]) {primes[++cnt] = i;min_primes[i] = i; // 記錄質數的最小質因數是其本身}for (int j = 1; primes[j] <= n / i; j++) {st[primes[j] * i] = true;min_primes[primes[j] * i] = primes[j]; // 記錄合數的最小質因數if (i % primes[j] == 0) {break;}}}
}
// 計算 x 的最小質因數
int D(int x) 
{if (x == 1) return 1;if (min_primes[x])return min_primes[x];else {cout << " 該數沒有找到最小質因數 ：" << endl;return 1e9;}
}
int main(void)
{cin >> n;get_primes(n);for (int i = 1; i <= n; i++) {cin >> a[i];}// 初始化 dp 數組for (int i = 1; i <= n; i++) {dp[i] = -1e9;}dp[1] = a[1];// 動態規劃計算for (int i = 2; i <= n; i++) {for (int j = 1; j < i; j++) {if (i <= j + D(n - j) && i <= n) {dp[i] = max(dp[i], dp[j] + a[i]);}}}cout << dp[n];return 0;
}