#1#4#8#9WA60求调
查看原帖
#1#4#8#9WA60求调
1256176
CQnythy2012楼主2025/7/3 13:32

前面有大佬说是dp数组赋值的问题,但是改成了-1e18还是错的TAT

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N=4010;
int T,maxP,W;
int ap[N],bp[N],as[N],bs[N];
int dp[N][N];//表示第i天后,拥有j张股票的最大收益 

signed main(){
	scanf("%lld%lld%lld",&T,&maxP,&W);
	for(int i=1;i<=T;i++){
		scanf("%lld%lld%lld%lld",&ap[i],&bp[i],&as[i],&bs[i]);
	}
	for(int i=0;i<=T;i++){
		for(int j=0;j<=maxP;j++){
			dp[i][j]=-1e18;
		}
	}
	dp[0][0]=0;
	deque<int> q1;
	deque<int> q2; 
	for(int i=1;i<=T;i++){
		for(int j=0;j<=as[i];j++){
			dp[i][j]=-j*ap[i];
		}
		if(i>1){
			for(int j=0;j<=maxP;j++){
				dp[i][j]=max(dp[i][j],dp[i-1][j]);
			}
		}
		if(i<=W) continue;
		//i-w-1天已有k股,再买j-k股 
		while(!q1.empty()) q1.pop_back();
		for(int j=0;j<=maxP;j++){
			while(!q1.empty()&&q1.front()<j-as[i]) q1.pop_front();//买入不够j 
			while(!q1.empty()&&dp[i-W-1][q1.back()]+q1.back()*ap[i]<dp[i-W-1][j]+j*ap[j]) q1.pop_back();//见DP课件-单调队列优化dp 
			q1.push_back(j);
			if(!q1.empty()){
				dp[i][j]=max(dp[i][j],dp[i-W-1][q1.front()]-ap[i]*(j-q1.front()));
			}
		}
		//i-w-1天已有k股,卖出k-j股 
		while(!q2.empty()) q2.pop_back();
		for(int j=maxP;j>=0;j--){
			while(!q2.empty()&&q2.front()>j+bs[i]) q2.pop_front();//卖出多余j 
			while(!q2.empty()&&dp[i-W-1][q2.back()]+q2.back()*bp[i]<dp[i-W-1][j]+j*bp[i]) q2.pop_back();
			q2.push_back(j);
			if(!q2.empty()){
				dp[i][j]=max(dp[i][j],dp[i-W-1][q2.front()]+bp[i]*(q2.front()-j));
			}
		}
	}
	cout<<dp[T][0];
	return 0;
} 
2025/7/3 13:32
加载中...