1 条题解
-
1梁文瀚LWH (winham) LV 10 @ 2023-7-30 15:39:13
#include<iostream> #include<string> #include<cctype> #include<cmath> #include<cstdlib> #include<cstring> #include<vector> #include<algorithm> #include<map> #include<set> #include<iomanip> using namespace std; #define int long long const int N = 2e5+10; const int INF = 0x3f3f3f3f3f3f3f3f; int n,m,a[N],dp[N],q[N],num[N],sum=0; signed main(){ //freopen("","r",stdin); //freopen("","w",stdout); cin>>n>>m; m++; for(int i=1;i<=n;i++){ cin>>a[i]; sum+=a[i]; } int l,r; l=r=1,q[r++]=0; for(int i=1;i<=n;i++){ while(l<r&&q[l]<=i-m-1)l++; dp[i]=a[i]+num[l]; while(l<r&&num[r-1]>dp[i])r--; num[r]=dp[i]; q[r++]=i; } int minn=INF; for(int i=n;i>n-m;i--)minn=min(minn,dp[i]); cout<<sum-minn<<endl; return 0; }
- 1
信息
- ID
- 2738
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 7
- 标签
- 递交数
- 14
- 已通过
- 10
- 上传者