hdu 3401 Trade 單調隊列優化dp

題目意思：

一個人開始有無窮多的錢，問買股票最多能賺多少錢。

要求：

每天買賣的股票數量有限制bl和sl，交易的時間間隔必須超過w+1天。

最多持有的數量為p股。

解題思路：

dp[i][j]表示前i天當持有j股股票時，獲得的最大利益。

狀態轉移：

當第i天不交易時為dp[i-1][j];

當第i天買(j-k)股時為dp[i-w-1][k]-(j-k)*b[i]   0=<k<=j  //注意要求第i-w----i-1天都不能交易.

     賣(k-j)股時為dp[i-w-1][k]+(k-j)*s[i]     j=<k<=p

當固定某個j時，dp[i-w-1][k]+k*b[i] 是固定的(k,j有個關系），所以可以用單調隊列優化。

代碼:

<SPAN style="FONT-SIZE: 18px">#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<stack>
#include<list>
#include<queue>
#define eps 1e-6
#define INF 0x1f1f1f1f
#define PI acos(-1.0)
#define ll __int64
#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
using namespace std;

/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
*/

int dp[2200][2200],b[2200],s[2200],bl[2200],sl[2200];
struct Node
{
   int nu,mo;
}myd[2200];


int main()
{
   int w,t,p,ca;

   scanf("%d",&ca);
   while(ca--)
   {
      scanf("%d%d%d",&t,&p,&w);
      for(int i=1;i<=t;i++)
         scanf("%d%d%d%d",&b[i],&s[i],&bl[i],&sl[i]);
      memset(dp,-INF,sizeof(dp));

      for(int j=1;j<=t;j++) //所有股票都是當天買的
         for(int i=0;i<=min(bl[j],p);i++)
            dp[j][i]=max(dp[j][i],-i*b[j]);

      for(int i=2;i<=t;i++)
      {
         dp[i][0]=0;
         for(int j=0;j<=p;j++)   //沒有交易
            dp[i][j]=max(dp[i-1][j],dp[i][j]);
        if(i<w+2)  //不能交易
            continue;

        int pre=i-w-1;
        int ss=0,e=-1;
        for(int j=0;j<=p;j++) //買
        {
           int tmp=dp[pre][j]+j*b[i];
            while(ss<=e&&tmp>=myd[e].mo)
                e--;
           struct Node te;
           te.nu=j,te.mo=tmp;
           myd[++e]=te;

           while(ss<=e&&j-myd[ss].nu>bl[i])
               ss++;
           dp[i][j]=max(dp[i][j],myd[ss].mo-j*b[i]);
        }
        ss=0,e=-1;
       // memset(myd,0,sizeof(myd));
        for(int j=p;j>=0;j--) //賣
        {
            int tmp=dp[pre][j]+j*s[i];
            while(ss<=e&&tmp>=myd[e].mo)
                e--;

            struct Node te;
            te.nu=j;te.mo=tmp;
            myd[++e]=te;
            while(ss<=e&&myd[ss].nu-j>sl[i])
                ss++;
            dp[i][j]=max(dp[i][j],myd[ss].mo-j*s[i]);

        }
      }
      int ans=0;

      for(int i=0;i<=p;i++)
        ans=max(ans,dp[t][i]);
      printf("%d\n",ans);

   }
   return 0;
}


</SPAN>