E—全都要！！！！！

原题：E—全都要！！！！！

题意：

给定 n 个数，从 0 开始向前移动，每次移动距离为 [1, 6]，移动过程 sum += a[i]，求经过确切的 k 次移动后 sum 最大值是多少？（进入数组需要一次移动）

思路：

dp

dp[i][j] 表示移动到 i 位置，移动 j 次的最优答案

• 遍历数组，枚举 j（因为要确切地移动 j 次，所以如果 i<k 那么就不能更新答案）
• 比较 i 的前 6 个位置，取最大值，注意不能越界

//      https://ac.nowcoder.com/acm/contest/102896/E
//      dp[i][j] 表示前 i 个位置移动 j 次的最优答案

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 1e9 + 7;
const int MIN = -1e18 - 7;

int T, n, m;
void solve()
{
    cin>>n>>m;
    vector<vector<int>> dp(n+1,vector<int>(m+1,MIN));
    vector<int> a(n+1);
    for(int i=1;i<=n;i++)cin>>a[i];
    int ans=MIN;
    dp[0][0]=0;//初始时为 0
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=min(i,m);j++)//因为要确切地走 j 步，所以如果 i<k 那么就不能更新答案
        {
            for(int k=max((int)0,i-6);k<i;k++)//看 i 位置的前 6 个位置，一定要正序遍历
            {
                dp[i][j]=max(dp[i][j],dp[k][j-1]+a[i]);
            }
        }
        ans=max(ans,dp[i][m]);
    }
    cout<<ans;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    T = 1;
    //cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}