首页 > 其他分享 >Cashback CF940E

Cashback CF940E

时间:2023-03-30 23:46:18浏览次数:43  
标签:CF940E int tt long Cashback include define

给你一个长度为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

相关文章

  • 题解 CodeForces 940E Cashback
    1.题面描述题目链接给定长为\(n\)的序列和一个整数\(c\),你需要将其分为若干段。对于每一段,若其长度为\(k\),则可以删除其中前\(\lfloor\frac{k}{c}\rfloor\)小的......