【 HDU 3401 】 Trade - 단조 로 운 대기 열 최적화 DP

테스트 주소: Trade
제목: 연속 T 일의 주식시장 상황 을 정 하고 네 개의 매개 변수 api, bpi, asi, bsi 를 포함한다. i 일 매입 가 는 api 1 주 이 고 판매 가 는 bpi 1 주 이 며 당일 최대 asi 주 를 살 수 있 고 최대 bsi 주 를 팔 수 있 으 며 하루 안에 매입 과 판매 에서 만 하 나 를 선택 할 수 있다. 또한 어느 날 수중 의 주식 이 max p 주 를 초과 하지 못 하도록 제한한다. 만약 에 하루 에 거래 (구 매 또는 판매) 를 하면그럼 앞으로 W 일 동안 거래 가 안 돼 요.처음에는 무한 한 원금 이 있 었 지만 주식 이 없어 서 마지막 에 최대 얼 마 를 벌 수 있 는 지 를 구 했다.
방법: 매일 조작 은 세 가지 가 있 습 니 다. 거래 하지 않 고, 사고, 팔 고.이 상태 이전 방정식 에 따라 dp [i] [j] 를 i 일 후에 손 에 j 주 를 가 진 최대 수익 으로 설정 하면:
dp[i][j]=max(dp[i-1][j],max(dp[x][k]-api*(j-k))(x≤i-w-1,kj));
초기 화: dp [0] [0] = 0, dp [i] [j] = - inf (i ≠ 0 및 j ≠ 0).
x 와 k 를 매 거 하면 O (T * maxp) 식 이 고 전체적인 복잡 도 는 O (T ^ 2 * maxp ^ 2) 에 이 르 러 화려 하 게 폭발 할 것 임 을 알 수 있 습 니 다.우 리 는 매 거 x 의 필요 성 을 고려 하여 우리 가 매번 dp [i] [j] 를 구 할 때마다 dp [i - 1] [j] 의 상황 을 고찰 해 야 한 다 는 것 을 발견 했다. 즉, dp [i] [j] ≥ dp [i - 1] [j] 이기 때문에 k 가 같은 상황 에서 dp [x] [k] 가 x 에서 최대 치 를 취 할 때 가장 크기 때문에 x 는 항상 i - w - 1 이 고 복잡 도 는 O (T * maxp ^ 2) 로 낮 아 져 도 이 문 제 를 통과 할 수 없다.다시 따로 사고 파 는 식 을 관찰 한 결과 모두 max (w [k]) + c (l ≤ k ≤ r) 의 형식 으로 변 할 수 있 음 을 발견 하 였 으 며, 사 는 식 에 대해 서 는 w [k] = dp [i - w - 1] [k] + api * k, c = - api * j, l = j - asi, r = j - 1, 파 는 식 이 같 음 을 발견 하 였 으 며, 우 리 는 i 와 j 가 같은 상황 에서 w [k] 는 k 가 유일 하 게 확 정 된 변수 (그리고 O (1) 로 계산 할 수 있 음) 이 며, c 는 상수 임 을 발견 하 였 다.또한 k 의 수치 범위 크기 는 항상 상수 이다. 이것 은 우리 가 단조 로 운 대기 열 을 사용 하여 최적화 하 는 것 을 시사 하기 때문에 복잡 도 를 O (T * maxp) 로 낮 추어 이 문 제 를 완벽 하 게 해결 하 는 것 을 의미한다.
다음은 본인 코드 입 니 다.

#include 
#include 
#include 
#include 
#include 
#define inf 2000000000
using namespace std;
int tt,T,maxp,w,api[2010],bpi[2010],asi[2010],bsi[2010];
int dp[2010][2010],h,t,q[2010];

int main()
{
  scanf("%d",&tt);
  while(tt--)
  {
    scanf("%d%d%d",&T,&maxp,&w);
	for(int i=1;i<=T;i++)
	  scanf("%d%d%d%d",&api[i],&bpi[i],&asi[i],&bsi[i]);
	
	for(int i=0;i<=T;i++)
	  for(int j=0;j<=maxp;j++)
	    dp[i][j]=-inf;
	dp[0][0]=0;
	for(int i=1;i<=T;i++)
	{
	  int s=max(0,i-w-1);
	  h=1,t=0;
	  for(int j=0;j<=maxp;j++)
	  {
	    dp[i][j]=max(dp[i][j],dp[i-1][j]);
		if (j>0)
		{
		  while(h<=t&&q[h]=dp[s][q[t]]+api[i]*q[t]) t--;
	      q[++t]=j-1;
		  dp[i][j]=max(dp[i][j],dp[s][q[h]]-api[i]*(j-q[h]));
		}
	  }
	  h=1,t=0;
	  for(int j=maxp;j>=0;j--)
	  {
	    if (jj+bsi[i]) h++;
		  while(h<=t&&dp[s][j+1]+bpi[i]*(j+1)>=dp[s][q[t]]+bpi[i]*q[t]) t--;
	      q[++t]=j+1;
		  dp[i][j]=max(dp[i][j],dp[s][q[h]]+bpi[i]*(q[h]-j));
		}
	  }
	}
    
	int ans=0;
	for(int i=0;i<=maxp;i++)
	  ans=max(ans,dp[T][i]);
	printf("%d
",ans);
  }
  
  return 0;
}