题解

题目要求到从第 $1$ 个格子跳到第 $n$ 个格子所能获得的最大分数，每次跳跃的距离必须是一个斐波那契数。

非常经典的一类 DP 题目了，定义 $dp[i]$表示跳到第 $i$ 个格子所能获得的最大分数。

显然，$dp[0] = w[0]$

• 对于$dp[i] (i > 0)$，可以枚举上一步跳跃的距离 $val$，如果 $val$ 是一个斐波那契数，并且 $i - val >= 0$，那么可以从第 $i - val$ 个格子跳到第 $i$ 个格子，此时获得的分数为 $dp[i - val] + w[i]$

可以预处理出所有不超过 $n$ 的斐波那契数

AC代码

C++

#include<bits/stdc++.h>
using namespace std;

#define int long long

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> w(n);
    for (int i = 0; i < n; ++i) {
        cin >> w[i];
    }

    vector<int> dp(n, -1e18);
    vector<int> a = {1, 1};
    while (a.back() < n) {
        a.push_back(a[a.size() - 1] + a[a.size() - 2]);
    }

    dp[0] = w[0];
    for (int u = 1; u < n; ++u) {
        for (int val : a) {
            if (val <= u) {
                dp[u] = max(dp[u], dp[u - val] + w[u]);
            }
        }
    }

    cout << dp[n - 1] << "\n";

    return 0;
}

java

import java.util.*;
class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] nums = new int[n];
        for(int i=0;i<n;i++) nums[i]=in.nextInt();
        long[] dp = new long[n];
        Arrays.fill(dp,Long.MIN_VALUE);
        dp[0]=nums[0];
        List<Integer> list = new ArrayList<>();
        list.add(1);list.add(1);
        int k=2;
        while(list.get(k-1)<n){
            int temp = list.get(k-1) + list.get(k-2);
            list.add(temp);
            k++;
        }
        for(int i=1;i<n;i++){
            for(int u : list){
                if(i-u>=0){
                    dp[i] = Math.max(dp[i], dp[i-u]+nums[i]);
                }else{
                    break;
                }
            }
        }
        System.out.println(dp[n-1]);
    }
}

Python

import java.util.*;
class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] nums = new int[n];
        for(int i=0;i<n;i++) nums[i]=in.nextInt();
        long[] dp = new long[n];
        Arrays.fill(dp,Long.MIN_VALUE);
        dp[0]=nums[0];
        List<Integer> list = new ArrayList<>();
        list.add(1);list.add(1);
        int k=2;
        while(list.get(k-1)<n){
            int temp = list.get(k-1) + list.get(k-2);
            list.add(temp);
            k++;
        }
        for(int i=1;i<n;i++){
            for(int u : list){
                if(i-u>=0){
                    dp[i] = Math.max(dp[i], dp[i-u]+nums[i]);
                }else{
                    break;
                }
            }
        }
        System.out.println(dp[n-1]);
    }
}

题目描述

小红小时候很喜欢一个叫跳格子的游戏，地上总共有$n$几个格子，小红跳到第$i$个格子可以获得$a_i$的分数。 小红从第1个格子开始，小红每次可以跳跃一个悲波那契数的长度，她想知道她恰好跳到第$n$个格子最多可以获得多少分。 所谓斐波那契数，指斐波那契数列:1,1,2,3,5,8.….中的某一项。悲波那契数列满足，第三项开始，每一项等于前两项之和。

输入描述

第一行输入一个整数$n(1\le n \le 2\times 10^5)$表示数组长度。

第二行输入$n$个整数表示每个格子的分数$a_i(-10^9\le a_i\le 10^9)$

输出描述

输出一个整数表示答案:

样例1

输入

3
1 2 3

输出

6

说明

第1步，跳跃1格，跳到第2个格子
第2步，跳跃1格，跳到第3个格子。
获得的分数为6。

样例2

输入

3
1 -2 3

输出

4