单调队列60pts,求Hack或指正
  • 板块P1833 樱花
  • 楼主suibian1234
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/4/14 16:56
  • 上次更新2024/4/14 20:16:23
查看原帖
单调队列60pts,求Hack或指正
329682
suibian1234楼主2024/4/14 16:56
#include<bits/stdc++.h>
using namespace std;
int n,m,w,v,d,dp[1001],l,r,tle[10005],GF;
int ccf(int x,int y){
	return dp[x]+((y-x)/w)*v;
}
int main(){
	scanf("%d:%d",&l,&r);
	scanf("%d:%d",&tle[0],&tle[1]);
	scanf("%d",&n);m=(tle[0]-l)*60+tle[1]-r;
	for(int i=0;i<n;i++){
		scanf("%d%d%d",&w,&v,&d);
		if(d==0)for(int j=w;j<=m;j++)dp[j]=max(dp[j],dp[j-w]+v);
		else{
			for(int j=0;j<w;j++){
				l=0,r=0;
				for(int k=0;(GF=k*w+j)<=m;k++){
					while(l<r&&tle[l]+d*w<GF)l++;
					while(l<r){
						if(ccf(tle[r-1],GF)<=dp[GF])r--;
						else break;
					}
					if(l<r)dp[GF]=ccf(tle[l],GF);
					tle[r++]=GF;
				}
			}
		}
	}
	GF=0;
	for(int i=1;i<=m;i++)GF=max(GF,dp[m]);
	cout<<GF;
	return 0;
}
2024/4/14 16:56
加载中...