1 条题解
- 
  1
#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
 - 上传者