社区讨论
那里出错了(求个助)
灌水区参与者 1已保存回复 1
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 1 条
- 当前快照
- 1 份
- 快照标识符
- @lo274cxm
- 此快照首次捕获于
- 2023/10/23 09:05 2 年前
- 此快照最后确认于
- 2023/11/03 09:20 2 年前
/*
5 2
1
2
3
4
5
应输出:12
*/
CPP#include <iostream>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#define N 100005
#define ull unsigned long long
using namespace std;
int n,m,a[N],num[N],head,tail;
ull sum[N],f[N][2],q[N];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]),sum[i]=sum[i-1]+a[i];
}
head=tail=1;
for(int i=1;i<=n;i++)
{
f[i][0]=max(f[i-1][0],f[i-1][1]);
f[i][1]=f[i][0];
while(num[head]<i-m&&head<=tail) head++;
f[i][1]=max(f[i][1],sum[i]+q[head]);
while(q[tail]<f[i][0]-sum[i]&&head<=tail) tail--;
q[++tail]=f[i][0]-sum[i]; num[tail]=i;
cout<<f[i][0]<<" "<<f[i][1]<<endl;
}
cout<<max(f[n][0],f[n][1]);
return 0;
}
回复
共 1 条回复,欢迎继续交流。
正在加载回复...