2025/1/20课堂记录

#include<iostream>
using namespace std;
int dp[51000],a[51000],n,t;
int check(int mid)
{
    for(int i=1;i<=mid+1;i++)dp[i]=a[i];//单调队列优化后，一个补0就能解决这行 
    for(int i=mid+2;i<=n;i++)
	{
	    dp[i]=0x3f3f3f3f;
		for(int j=i-mid-1;j<=i-1;j++)dp[i]=min(dp[j]+a[i],dp[i]);	
    } 
    int ans=0x3f3f3f3f;
    for(int i=n-mid;i<=n;i++)ans=min(ans,dp[i]);
	return ans<=t;
} 

int main()
{
	cin>>n>>t;
	for(int i=1;i<=n;i++)cin>>a[i];
	int l=0,r=n,ans=0x3f3f3f3f;
	while(l<=r)
	{
		int mid=(l+r)/2;
		if(check(mid))r=mid-1,ans=mid;
		else l=mid+1;
	}
	cout<<ans<<endl;
	return 0; 
}

 #include<iostream>
using namespace std;
int n,m,a[200010],q[200010];
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		int x;
		cin>>x;
		a[i]=a[i-1]+x;
	}
	int l=0,r=1,ans=-0x3f3f3f3f;
	for(int i=1;i<=n;i++)
	{
		while(l<r&&q[l]<i-m)l++;
		ans=max(ans,a[i]-a[q[l]]);
		while(l<r&&a[q[r-1]]>a[i])r--;
		q[r++]=i;
	}
	cout<<ans;
	return 0;
}

 //https://blog.csdn.net/ybC202444/article/details/127161633
//修建草坪,朴素dp 
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5 ;
#define  ll  long long
ll n,k,a[MAXN],q[MAXN];
ll s[MAXN],dp[MAXN][2];
ll l,r; 
// dp[i][0]: 第i个数不要，1-i之间，最大效率；
// dp[i][1]: 第i个数要，1-i之间，最大效率；
int main()
{
	cin>>n>>k;
	for(ll i=1;i<=n;i++)
	{
		cin>>a[i];
		s[i]=s[i-1]+a[i];
	}
	l=0,r=0;
	q[l]=0,r=1;// 队头插入0编号
	//单调队列维护 
	for(ll i=1;i<=n;i++)
	{
		while(l<r&&q[l]<i-k)l++;
		dp[i][0]=max(dp[i-1][1],dp[i-1][0]);
		dp[i][1]=dp[q[l]][0]+s[i]-s[q[l]];//j不要，j+1---i要
		//dp[i][1]=(dp[q[l]][0]-s[q[l]]) + s[i]
		//f[i]=max/min(g(j))+a[i] 
		//维护递减： dp[j][0]-s[j]   
		while(l<r&&dp[q[r-1]][0]-s[q[r-1]]<dp[i][0]-s[i])r--;
		q[r++]=i;
	}
	printf("%lld\n",max(dp[n][1],dp[n][0]));
}