单调队列优化DP ：
dp[ i ] [ j ] = max{ dp[ i-1 ] [ j ]  ,  dp[ i - w -1 ] [ k ] - ( j - k )*ap[ i ]  ,  dp [ i - w - 1 ] [ k ] + ( k - j )*bp[ i ]  }
后两项 dp [ i - w - 1 ][ k ] + k* xx - j * xx 且 abs( j - x) < yy 可以维护一个单调递减的队列。。。

Trade

1
5 2 0
2 1 1 1
2 1 1 1
3 2 1 1
4 3 1 1
5 4 1 1

3

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <algorithm>

using namespace std;

const int maxn=2200;

int N,P,W,dp[maxn][maxn],ap[maxn],bp[maxn],as[maxn],bs[maxn];

struct node
{
    int val,pos;
}que[maxn];

void solve()
{
    int head,tail,pre;

    memset(dp,0xcf,sizeof(dp));

    for(int i=1;i<=N;i++)
    {
        for(int j=0;j<=min(as[i],P);j++)
        {
            dp[i][j]=-ap[i]*j;
        }
    }

    for(int i=2;i<=N;i++)
    {
        for(int j=0;j<=P;j++)
        {
            dp[i][j]=max(dp[i-1][j],dp[i][j]);
        }
    }

    for(int i=W+2;i<=N;i++)
    {
        pre=i-W-1;
        head=0,tail=-1;
        for(int j=0;j<=P;j++)///buy
        {
            dp[i][j]=max(dp[i-1][j],dp[i][j]);

            node temp;
            temp.val=dp[pre][j]+j*ap[i];
            temp.pos=j;

            while(head<=tail&&que[tail].val<temp.val) tail--;
            que[++tail]=temp;
            while(head<=tail&&(j-que[head].pos)>as[i]) head++;

            if(head<=tail)
            {
                dp[i][j]=max(dp[i][j],que[head].val-j*ap[i]);
            }
        }

        head=0;tail=-1;
        for(int j=P;j>=0;j--)///sell
        {
            dp[i][j]=max(dp[i-1][j],dp[i][j]);

            node temp;
            temp.val=dp[pre][j]+bp[i]*j;
            temp.pos=j;

            while(head<=tail&&que[tail].val<temp.val) tail--;
            que[++tail]=temp;
            while(head<=tail&&(que[head].pos-j)>bs[i]) head++;

            if(head<=tail)
            {
                dp[i][j]=max(dp[i][j],que[head].val-bp[i]*j);
            }
        }
    }
}

int main()
{
    int cas;
    scanf("%d",&cas);
while(cas--)
{
    scanf("%d%d%d",&N,&P,&W);
    for(int i=1;i<=N;i++) scanf("%d%d%d%d",ap+i,bp+i,as+i,bs+i);
    solve();
    printf("%d\n",dp[N][0]);
}
    return 0;
}

夏令时【Daylight Saving Time】时间计算出错的解决办法

原文：http://blog.csdn.net/jcx5083761/article/details/19864715