C++问题，具体问题看截图

训练计划
难度：
时间限制：1s
内存限制：128M
开始编程
【题目描述】
小九是个天赋异禀的。尤其在信息学方面，学习不满一年，他的成绩便已远远超出了学校里久居机房的高年级们。天赋固然重要，但小九知道，要早日实现他的真正目标，努力必不可少。为此，小九制定了一项训练计划。
他的训练计划共包括N个习题，编号1∼N，第i个习题能为小九带来收获值g
i
​
。迫不及待的小九，今天就开始执行自己的训练计划了。他会以每天一题的速度，按顺序做题。
当然，小九并不想让自己的训练过程过于枯燥，因此对于任意连续编号的习题而言，小九至多只会选择其中的K题。
现在，小九想提前知道，当他完成此项训练计划时，他所选择的习题的收获值的乘积，最大会是多少？
【输入格式】
第一行，两个整数N、K，意义如上。
第二行，N个用空格分隔的整数，其中第i个整数表示相应编号习题的收获值g
i
​
。
【输出格式】
一个整数，表示所选习题的最大收获值乘积。输出计算结果对10
9
+7取模后的数值即可。
【输入输出样例#1】
输入#1
4 2
2 5 3 5
复制
输出#1
50
复制
【说明提示】
样例最优方案是选择第1∼2、4个习题，其收获值的乘积为50。虽然选择第2∼4个习题，收获值的乘积更大，但这个方案不满足"连续编号习题至多只选K=2题"的要求。
【数据范围】
对于15%的数据，保证1≤N≤20。
对于30%的数据，保证1≤N≤100。
对于70%的数据，保证1≤N≤10
4
。
对于100%的数据，保证1≤K≤N≤10
6
，1≤g
i
​
≤9。

N=100的话，用dfs遍历下就可以了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7,maxn=1e6+10;
int n,k;
ll num[maxn],L[maxn],R[maxn],s[maxn];
int stk[maxn],top;
inline void init(int &x){
    scanf("%d",&x);
}
char buf[10000030],*p;//缓冲区
#define getchar() p==buf&&(p=buf+fread(buf,1,10000000,stdin),p==buf)?EOF:*p++;
inline void read(ll &x){
    x=0;char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();
}
int main(){
    fread(buf,1,10000000,stdin);p=buf;
    init(n),init(k);
    for(register int i=1;i<=n;i++){
        read(num[i]);
        s[i]=s[i-1]+num[i];//求前缀和数组
    }
    for(register int i=1;i<=n;i++){
        while(top&&num[i]<num[stk[top]]) top--;//维护一个单调递增的单调栈
        L[i]=stk[top];
        stk[++top]=i;
    }
    top=0;
    for(register int i=n;i>0;i--){//同样道理，只不过是倒序扫
        while(top&&num[i]<num[stk[top]]) top--;
        R[i]=stk[top];
        stk[++top]=i;
    }
    ll ans=0;
    for(register int i=1;i<=n;i++){
        ll L1=s[i-1]-s[L[i]-1];//分割之前那部分的和
        ll R1=s[R[i]-1]-s[i-1];//分割之后那部分的和
        ll x=L1+num[i],y=s[R[i]-1]-s[L[i]],z=num[i]+R1;//即为题目中的 i+k-1 时的值
        ll tmp=max(x,max(y,z));
        ans=max(ans,tmp);
    }
    printf("%lld\n",ans%mod);
    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 1000010, mod = 1e9 + 7;

int n, k;
int w[N];
int q[N], hh, tt = -1;
LL f[N];

int main()
{
cin >> n >> k;
for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);

for (int i = 1; i <= n; i ++ )
{
    if (hh <= tt && i - k > q[hh]) hh ++ ;
    if (hh <= tt) f[i] = f[q[hh]] + w[i] * w[q[hh]];
    while (hh <= tt && f[q[tt]] + w[q[tt]] * w[i] <= f[i] + w[i] * w[q[hh]]) tt -- ;
    q[ ++ tt] = i;
}

LL res = 0;
for (int i = n - k + 1; i <= n; i ++ )
    res = max(res, f[i]);

cout << res % mod << endl;
return 0;
}