[동적 기획] [SCOI 2011] 주식 거래

【    】
  lxhgww        ，            ，              。
         ，lxhgww      T         ， i          APi， i          BPi（        i，  APi>=BPi），            ，          i            ASi ，          BSi 。
  ，             。          ，            （                 ）  ，     W ，        i      ，    i+1   i+W ，       。  ，      ，             ，              MaxP。
  1   ，lxhgww       （          ），        ，  ，T   ，lxhgww        ，       ，       ？
【  】
         3   ，   T，MaxP，W。
   T ， i    i-1      ，  4   ，    APi，BPi，ASi，BSi。
【  】
       ，  1   ，  lxhgww         。
【    】
5 2 0
2 1 1 1
2 1 1 1
3 2 1 1
4 3 1 1
5 4 1 1
【    】
    3
【    】
     30%   ，0<=W<T<=50,1<=MaxP<=50
     50%   ，0<=W<T<=2000,1<=MaxP<=50
     100%   ，0<=W<T<=2000,1<=MaxP<=2000

          ，1<=BPi<=APi<=1000,1<=ASi,BSi<=MaxP

이 문제 의 동적 계획 의 단조 로 운 대기 열 최적화.소박 한 방법 은 다음 과 같다. 상태: f [i] [j] 로 전날 중 마지막 1 일 장 을 마 칠 때 수중 에 j 주 를 보유 한 주식 이 얻 을 수 있 는 최대 수익 을 나타 낸다.전이 방정식: f [i] [j] = max {f [i - 1] [j], f [i - W - 1] [j - k1] - ap [i] * k1, f [i - W - 1] [j + k2] + bp [i] * k2}.그 중에서 k1 < = as [i], k2 < = bs [i].상기 알고리즘 의 복잡 도 는 O (T * maxP ^ 2) 로 극한 데 이 터 를 넘 지 못 한 것 이 분명 하 다.상기 전이 방정식 방정식 에 대해 다음 과 같은 전환 을 할 수 있다. 령 t = i - W - 1, p = j - k1, q = j + k2.f [i - 1] [j] 항목 을 무시 하면 f [i] [j] = max {f [t] [p] - ap [i] * (j - p), f [t] [q] + bp [i] * (q - j)}, 그리고 p > = j - as [i], q < = j + bs [i] 가 있 습 니 다.즉 f [i] [j] = max (f [t] [p] + ap [i] * p - ap [i] * j,    (1)                 f[t][q] + bp[i] * q - bp[i] * j}。  (2) 이렇게 하면 (1) 식 에서 f [t] [p] + ap [i] * p 부분 과 (2) 식 에서 f [t] [q] + bq [i] * q 부분 은 p, q 와 만 관련 되 기 때문에 단조 로 운 대기 열 을 사용 하여 최적화 할 수 있 습 니 다.
자세 한 내용 은 프로그램 설명 을 보십시오. Accode:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <bitset>

using std::max;

const int maxN = 2010;
const int MAX = 0x3f3f3f3f;
const int MIN = ~MAX;

int F[maxN][maxN];
int q[maxN];
int val[maxN];
int ap, bp, as, bs;
int n, W, Lim, f, r;

int main()
{
	freopen("trade.in", "r", stdin);
	freopen("trade.out", "w", stdout);
    scanf("%d%d%d", &n, &Lim, &W);
    int ans = 0;
    memset(F, 0xc0, sizeof(F));
    F[0][0] = 0;
    for (int i = 1; i < n + 1; ++i)
    {
        scanf("%d%d%d%d", &ap, &bp, &as, &bs);
        for (int j = 0; j < as + 1; ++j) F[i][j] = -ap * j;
	//    i, j       ，
	//    1 <= i <= W    。
        for (int j = 0; j < Lim + 1; ++j)
            F[i][j] = max(F[i][j], F[i - 1][j]);
	//           。
        int t = i - W - 1;
        if (t >= 0)
        {
            f = r = 0; //    。
            for (int j = 0; j < Lim + 1; ++j)
            {
                while (f < r && q[f] < j - as) ++f;
		//      p     p >= j - as[i]。
                while (f < r && F[t][j] + j * ap >= val[r - 1])
                    --r;
		//         ，     。
                val[r] = F[t][j] + j * ap;
                q[r++] = j;
		//  。
                if (f < r) F[i][j] = max(F[i][j], val[f] - j * ap);
		//      ，   F[i][j]  。
            } //Buy.
            f = r = 0;
            for (int j = Lim; j > -1; --j)
            {
                while (f < r && q[f] > j + bs) ++f;
		//      p     p <= j + bs[i]。
                while (f < r && F[t][j] + j * bp >= val[r - 1])
                    --r;
		//         ，     。
                val[r] = F[t][j] + j * bp;
                q[r++] = j;
		//  。
                if (f < r) F[i][j] = max(F[i][j], val[f] - j * bp);
		//      ，   F[i][j]  。
            } //Sell.
        }
        ans = max(F[i][0], ans);
    }
    printf("%d
", ans);
	return 0;
}