Cptraser/ 十一月 2, 2018/ 2018.11/ 0 comments

[SCOI2010]股票交易

题面传送门

    \[F(i,j)=F(i-1,j)\]

    \[F(i,j)=F(i-w-1,k)-(j-k) * AP_i (k<j)\]

    \[F(i,j)=F(i-w-1,k)+(k-j) * BP_i (k>j)\]

用单调队列维护F(i-w-1,k)+k * AP_i(BP_i)即可。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int T,MaxP,W,a,b,c,d,F[2005][2005],L[2005],Ans;
int main()
{
    scanf("%d%d%d",&T,&MaxP,&W);
    memset(F,-63,sizeof F);
    for(int i=1;i<=T;i++){
        scanf("%d%d%d%d",&a,&b,&c,&d);
        for(int j=0;j<=MaxP;j++)F[i][j]=F[i-1][j];
        for(int j=0;j<=c;j++)F[i][j]=max(F[i][j],-a*j);
        int Pre=i-W-1;
        if(Pre<0)continue;
        int head=1,tail=0;
        for(int j=0;j<=MaxP;j++){
            while(head<=tail&&j-L[head]>c)head++;
            if(head<=tail)F[i][j]=max(F[i][j],F[Pre][L[head]]+L[head]*a-j*a);
            while(head<=tail&&F[Pre][j]+j*a>F[Pre][L[tail]]+L[tail]*a)tail--;
            L[++tail]=j;
        }
        head=1,tail=0;
        for(int j=MaxP;~j;j--){
            while(head<=tail&&L[head]-j>d)head++;
            if(head<=tail)F[i][j]=max(F[i][j],F[Pre][L[head]]+L[head]*b-j*b);
            while(head<=tail&&F[Pre][j]+j*b>F[Pre][L[tail]]+L[tail]*b)tail--;
            L[++tail]=j;
        }
    }
    printf("%d\n",F[T][0]);
}
Share this Post

Leave a Comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>
*
*