关于卖出时的转移顺序
查看原帖
关于卖出时的转移顺序
450743
XOOR楼主2024/10/15 15:57

为什么不能这样转移,从初始位置 00 先将 bsibs_idplst,jdp_{lst,j} 元素放入队列中,然后转移的时候每次只向后考虑一位

int lst=i-W-1;
if(lst<1) continue ;
for(int j=1;j<=bs[i];j++){//q2
	while(l2<=r2 && dp[lst][q2[r2]]+q2[r2]*bp[i]<=dp[lst][j]+j*bp[i]) r2--;
	q2[++r2]=j;
}
for(int j=0;j<=MaxP;j++){
	if(l2<=r2) chkmax(dp[i][j],dp[lst][q2[l2]]+q2[l2]*bp[i]-j*bp[i]);
	l2++;
	while(l2<=r2 && dp[lst][q2[r2]]+q2[r2]*bp[i]<=dp[lst][j+bs[i]+1]+(j+bs[i]+1)*bp[i]) r2--;
	q2[++r2]=j+bs[i]+1;
}
2024/10/15 15:57
加载中...