记录编号	581592	评测结果	AAAAAAAAAA
题目名称	[SCOI 2010]股票交易	最终得分	100
用户昵称	小金	是否通过	通过
代码语言	C++	运行时间	0.540 s
提交时间	2023-08-06 17:22:32	内存使用	16.92 MiB

#include<iostream>
#include<cstring>
using namespace std;
int f[2010][2010],n,m,w,ap,bp,as,bs,l,r,q[2010],ans=0;
int main()
{
    freopen("stock.in","r",stdin);
    freopen("stock.out","w",stdout);
    memset(f,128,sizeof(f));//赋值为-inf 
    cin>>n>>m>>w;
    for(int i=1;i<=n;i++)
    {
        cin>>ap>>bp>>as>>bs;
        for(int j=0;j<=as;j++)
        {
            f[i][j]=-1*j*ap;
        }
        for(int j=0;j<=m;j++)
        {
            f[i][j]=max(f[i][j],f[i-1][j]);
        }
        if(i<=w)
        {
            continue;
        }
        l=1;
        r=0;
        for(int j=0;j<=m;j++)
        {
            while(l<=r&&q[l]<j-as)
            {
                l++;
            }
            while(l<=r&&f[i-w-1][q[r]]+q[r]*ap<=f[i-w-1][j]+j*ap)
            {
                r--;
            }
            r++;
            q[r]=j;
            if(l<=r)
            {
                f[i][j]=max(f[i][j],f[i-w-1][q[l]]+q[l]*ap-j*ap);
                
            }
        }
        l=1;
        r=0;
        for(int j=m;j>=0;j--)
        {
            while(l<=r&&q[l]>j+bs)
            {
                l++;
            }
            while(l<=r&&f[i-w-1][q[r]]+q[r]*bp<=f[i-w-1][j]+j*bp)
            {
                r--;
            }
            r++;
            q[r]=j;
            if(l<=r)
            {
                f[i][j]=max(f[i][j],f[i-w-1][q[l]]+q[l]*bp-j*bp);
            }
        }
    }
    for(int i=0;i<=m;i++)
    {
        ans=max(ans,f[n][i]);
    }
    cout<<ans;
    return 0;
}