给你一个长度为n的数列a和整数c
你需要把它任意分段
每一段假设长度为k,就去掉前[ k/c] ( 向下取整)小的数
最小化剩下的数的和
#include<iostream> #include<algorithm> #include<cstring> #include<queue> #define IOS std::ios::sync_with_stdio(0) using namespace std; const int N=1e5+20; #define int long long int a[N],s[N],f[N],g[N],C,n; int hh,tt,q[N]; signed main(){ int i; cin>>n>>C; for(i=1;i<=n;i++) cin>>a[i],s[i]=s[i-1]+a[i]; hh=1,tt=0; q[++tt]=0; for(i=1;i<=n;i++){ while(hh<=tt&&q[hh]<=i-C) q[hh++]=0; g[i] = a[q[hh]]; while(hh<=tt&&a[i]<=a[q[tt]]) q[tt--]=0; q[++tt]=i; } for(i=1;i<C;i++) f[i]=f[i-1]+a[i]; for(i=C;i<=n;i++){ f[i]= min( f[i-1]+a[i],f[i-C]+ s[i]-s[i-C]-g[i]); } cout<<f[n] ; }
标签:CF940E,int,tt,long,Cashback,include,define From: https://www.cnblogs.com/towboa/p/17274796.html