最近遇到不少DP优化的题，感觉这方面还有些欠缺，现在就多做点这方面的题，练练手。

这题是道较为经典的单调队列优化的题，总共有三种状态，买，卖及其他。

对于买:dp[i][j] = max(dp[i][j],dp[x][y] - (j-y)*sell) (y<=j && y+买的限制>=j &&  0 <= x <= i-w-1)

对于卖:dp[i][j] = max(dp[i][j],dp[x][y] + (y-j)*buy) (y >= j && j + 卖的限制 >= y && 0 <= x <= i-w-1)。

优化主要在T，和MAXP上。

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #define MAXN 2012 7 #define INF -(1<<29) 8 using namespace std; 9 int dp[MAXN][MAXN];10 int b_price[MAXN];11 int s_price[MAXN];12 int b_stock[MAXN];13 int s_stock[MAXN];14 15 void get_dp(int n, int w, int p)16 {17     int ans = INF;18     dp[0][0] = 0;19     int b[MAXN];20     int s[MAXN];21     for (int i(0); i
           
             w) {27 while (b_h != b_e && b[b_h+1] + b_stock[i] < j) ++b_h;28 while (s_h != s_e && s[s_h+1] < j) ++s_h;29 30 while (b_h != b_e && dp[i-w-1][b[b_e]] - b_price[i]*(j-b[b_e]) < dp[i-w-1][j])--b_e;31 b[++b_e] = j;32 dp[i][j] = max(dp[i][j],dp[i-w-1][b[b_h+1]]-b_price[i]*(j-b[b_h+1]));33 while (j + s_stock[i] >= k && k <= p) {34 while (s_h != s_e && dp[i-w-1][s[s_e]] + s_price[i]*(s[s_e]-j) < dp[i-w-1][k] + s_price[i]*(k-j))--s_e;35 s[++s_e] = k;36 ++k;37 }38 dp[i][j] = max(dp[i][j],dp[i-w-1][s[s_h+1]]+s_price[i]*(s[s_h+1]-j));39 }40 ans = max(ans,dp[i][j]);41 }42 }43 cout<
            
             <