题解 | #E-全都要！！！！！#

E-全都要！！！！！_牛客周赛 Round 83

分析题目：题目给出每次只可以在1~6跳，最后选择k个值，得出最大值。 思路：首先，最容易想到的就是DFS暴力搜索，即选择所有的可能进行找寻，进而比较出一个最大的值。->但是会超时

暴搜：

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e4+9;
int a[N];
ll ans;
int n,k;
void DFS(int st,int dep,ll res){
    if(dep==k){
        ans=max(ans,res);
        return;
    }
    for(int i=st+1;i<=st+6;i++){
        DFS(i,dep+1,res+a[i]);
    }
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>k;
    ans=0x8000000000000000;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=6;i++)DFS(i,1,a[i]);
    cout<<ans;
    return 0;
}

这时就要想，哪里可以优化。我们可以思考一下，发现我们如果从下往上就可以存储每个以st为起点且剩余k-dep个数未选的最大值。在之后的向下遍寻路径中，我们判断如果result数组不是初始值，就可以直接用，不用继续往下找了

记忆化搜索：

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e4+9;      // 数组大小上限，用于存储输入的数字
const int M=1e3+9;      // 记忆化搜索状态数组的第二维大小
const ll inf=0x8000000000000000;  // 负无穷，用于初始化和比较
int a[N];               // 存储输入的数字
ll ans,result[N][M];    // ans存储最终答案，result用于记忆化搜索
int n,k;                // n是数组长度，k是需要选择的数字个数

ll DFS(int st,int dep){
    // 如果已经选择了k个数，直接返回当前位置的值
    if(dep==k)return a[st];
    
    // 如果已经计算过这个状态，直接返回缓存的结果
    if(result[st][k-dep]!=inf)return result[st][k-dep];
    
    // 尝试从当前位置后面1到6步内选择下一个位置
    for(int i=st+1;i<=st+6&&i<=n;i++){
        ll tmp=a[st];  // 当前位置的值
        tmp+=DFS(i,dep+1);  // 加上从下一个位置开始的最大和
        result[st][k-dep]=max(result[st][k-dep],tmp);  // 更新最大值
    }
    return result[st][k-dep];  // 返回从当前位置开始的最大和
}

int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>k;
    ans=inf;    // 初始化答案为负无穷
    
    for(int i=1;i<=n;i++)cin>>a[i];
    
    // 初始化记忆化搜索数组
    for(int i=1;i<=n;i++){
        for(int j=1;j<=k;j++)result[i][j]=inf;
    }
    
    // 尝试从前6个位置开始，找出最大的和
    for(int i=1;i<=6;i++)ans=max(DFS(i,1),ans);
    
    cout<<ans;  // 输出结果
    return 0;
}