传送门

---

解题思路

首先 \(t\) 可以直接算出来：\(t=\left \lceil \dfrac{n}{k} \right \rceil\)

我们从最朴素的 dp 开始想。

设 \(dp(i,j)\) 表示前 \(i\) 天，浏览了 \(j\) 个景点的最大评分。

那么转移方程为：

\[dp(i,j)=\max_{x=j-k}^{j-1}(dp(i-1,x)+\max(a_{x+1},a_{x+2},\cdots,a_j)) \]

我们发现因为要保证用最少的天数浏览，所以可以把原转移方程改为：

\[dp(i,j)=\max_{x=j-k}^{j-1}(dp(i-1,x)+\max(a_{x+1},a_{x+2},\cdots,a_j)-inf) \]

Q：有什么用呢？

A：第一维可以直接省掉了，\(dp(j)\) 的意义变为用最少的天数浏览前 \(j\) 个景点的最大评分。

转移方程变为：

\[dp(i)=\max_{j=i-k}^{i-1}(dp(j)+\max(a_{j+1},a_{j+2},\cdots,a_i)-inf) \]

但是这样还需要枚举 \(x\)，复杂度仍为 \(O(nk)\)，需要继续进行优化。因为已经优化完状态设计了，所以我们把下一步优化放在优化转移上。

令 \(maxx(j,i)\) 表示 \(a_j\) 到 \(a_i\) 的最大值，则在 \(i\) 固定的时候，\(maxx(j,i)\) 的值是随着 \(j\) 的增大而呈区间变小的，这样我们可以用线段树维护区间的最大值，维护的信息为 \(dp[j]+maxx(j+1,i)\)。

需要进行的操作即为单点更新 \(dp[j]\)，区间修改，和区间查询最大值 \((i-k)\to (i-1)\)。

线段树维护一下即可。

总时间复杂度为 \(O(nlogn)\)。

注意：

• update传的参数v需要用long long。
• ceil函数默认返回值是double，而double没有long long范围大，需要先强制转换为long long类型，不然会wa掉。

（调了一晚上交了二十多遍的我瑟瑟发抖）

AC代码

#include<cstdio>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cmath>
#include<algorithm>
#include<stack>
using namespace std;
const int maxn=1e6+5;
const long long inf=1e12;
long long dp[maxn],d[maxn*6],lazy[maxn*6],a[maxn],s[maxn],n,k,last;
inline void pushdown(int id){
	if(lazy[id]==0) return;
	lazy[id*2]+=lazy[id];
	lazy[id*2+1]+=lazy[id];
	d[id*2]+=lazy[id];
	d[id*2+1]+=lazy[id];
	lazy[id]=0;
}
inline void pushup(int id){
	d[id]=max(d[id*2],d[id*2+1]);
}
void update(int id,int l,int r,int x,int y,long long v){
	if(x<=l&&r<=y){
		lazy[id]+=v;
		d[id]+=v;
		return;
	}
	int mid=(l+r)/2;
	pushdown(id);
	if(x<=mid) update(id*2,l,mid,x,y,v);
	if(y>mid) update(id*2+1,mid+1,r,x,y,v);
	pushup(id);
}
long long query(int id,int l,int r,int x,int y){
	if(x<=l&&r<=y){
		return d[id];
	}
	int mid=(l+r)/2;
	pushdown(id);
	long long res=-9e18;
	if(x<=mid) res=max(res,query(id*2,l,mid,x,y));
	if(y>mid) res=max(res,query(id*2+1,mid+1,r,x,y));
	return res;
}
int main(){
	ios::sync_with_stdio(false);
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=n;i++){
		while(last&&a[s[last]]<=a[i]){//单调栈更新
			update(1,0,n,s[last-1],s[last]-1,a[i]-a[s[last]]);//因为maxx(j,i)改变了，所以需要在线段树中进行更新
			last--;
		}
		s[++last]=i;
		update(1,0,n,i-1,i-1,dp[i-1]+a[i]);
		dp[i]=query(1,0,n,max((long long)0,i-k),i-1)-inf;//状态转移
	}
	cout<<(long long)(dp[n]+(long long)ceil((double)1.0*n/k)*inf);
    return 0;
}