【题目链接】 点击打开链接


【题意】 大概就是说一个人现在炒股，他有两种操作，一种是买股票（这个当然是花钱）， 一个是卖股票（这里钦定为挣钱）。然后每个人在每天买和卖股票的数量是有限制的，并且还有一个限制是一个人拥有的股票数不能超过MaxP。还有一个人执行操作的间隔必须大于W。问这个人最后最多挣多少钱？


【解题方法】


我们可以大胆的写出一个朴素的DP方程：
    dp[i][j] 表示第 i 天，拥有股票数目为 j 的时候赚了多少钱？
那么DP分为3种情况：
   （1） 前一天不买不卖，从前一天转移过来
         dp[i][j] = max(dp[i][j], dp[i-1][j])
   （2） 前i - w - 1天买进一些股。
         dp[i][j] = max(dp[i][j], dp[i - w - 1][k] + (j - k) * AP[i])；
   （3） 前i - w - 1天卖掉一些股。
         dp[i][j] = max(dp[i][j], dp[i - w - 1][k] + (k - j) * BP[i]);

好的，到现在为止，我们的朴素DP方程就推完了，或许这里有个疑惑？为什么是从i - w - 1转移就行了呢？ 这里考虑下 i - w - 1的状态 可以由 i - w - 2的状态不买不卖，
转移过来， 那么我们就可以放心的使用这个DP了。
    我们来想一下这个DP的复杂度？
    枚举i, j, k 显然是 O(Maxp * n * n)， 这显然炸掉的复杂度， 题目只有1000ms。那么我们怎么优化呢？ 我们把DP来变一下形状，发现第2个dp可以写成 ：
    dp[i][j] = max(dp[i - w - 1][k] - (j * AP[i] - k * AP[i])
             = dp[i - w - 1][k] + k * AP[i] - j * AP[i];
    让f[i - 1][j] = dp[i - w - 1][k] + k * AP[i];
      g[i][j] = - j * AP[i];
    这个式子又转化成了标准的单调队列优化，我们的复杂度可以顺利降为 O(MaxP * n)， 就可以通过这个题了。

【AC代码】 
//
//Created by BLUEBUFF 2016/1/8
//Copyright (c) 2016 BLUEBUFF.All Rights Reserved
//

#pragma comment(linker,"/STACK:102400000,102400000")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdio>
#include <time.h>
#include <cstdlib>
#include <cstring>
#include <sstream> //isstringstream
#include <iostream>
#include <algorithm>
using namespace std;
//using namespace __gnu_pbds;
typedef long long LL;
typedef pair<int, LL> pp;
#define REP1(i, a, b) for(int i = a; i < b; i++)
#define REP2(i, a, b) for(int i = a; i <= b; i++)
#define REP3(i, a, b) for(int i = a; i >= b; i--)
#define CLR(a, b)     memset(a, b, sizeof(a))
#define MP(x, y)      make_pair(x,y)
const int maxn = 220;
const int maxm = 2e5;
const int maxs = 10;
const int maxp = 1e3 + 10;
const int INF  = 1e9;
const int UNF  = -1e9;
const int mod  = 1e9 + 7;
int gcd(int x, int y) {return y == 0 ? x : gcd(y, x % y);}
//typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>order_set;
//head

struct node{
    int pos, f;
}que1[2010];//维护单调递减栈
int AP[2010], BP[2010], AS[2010], BS[2010];
int dp[2010][2010];
int n, MaxP, w, head1, tail1;

int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d%d%d", &n, &MaxP, &w);
        for(int i = 1; i <= n; i++) scanf("%d%d%d%d", &AP[i], &BP[i], &AS[i], &BS[i]);
        //init
        head1 = tail1 = 0;
        CLR(que1, 0);
        for(int i = 0; i <= n; i++){
            for(int j = 0; j <= MaxP; j++){
                dp[i][j] = UNF;
            }
        }
        for(int i = 1; i <= w + 1; i++){
            for(int j = 0; j <= min(MaxP, AS[i]); j++){
                dp[i][j] = -AP[i] * j;
            }
        }
        dp[0][0] = 0;
        //
        for(int i = 1; i <= n; i++){//枚举天数
            for(int j = 0; j <= MaxP; j++){
                dp[i][j] = max(dp[i][j], dp[i-1][j]);
            }
            if(i <= w + 1) continue;
            head1 = tail1 = 0;
            for(int j = 0; j <= MaxP; j++){
                int nowf = dp[i - w - 1][j] + j * AP[i];
                while(head1 < tail1 && que1[head1].pos + AS[i] < j) head1++;
                while(head1 < tail1 && que1[tail1 - 1].f < nowf) tail1--;
                que1[tail1].f = nowf, que1[tail1].pos = j; tail1++;
                dp[i][j] = max(dp[i][j], que1[head1].f - j * AP[i]);
            }
            head1 = tail1 = 0;
            for(int j = MaxP; j >= 0; j--){
                int nowf = dp[i - w - 1][j] + j * BP[i];
                while(head1 < tail1 && que1[head1].pos - BS[i] > j) head1++;
                while(head1 < tail1 && que1[tail1 - 1].f < nowf) tail1--;
                que1[tail1].f = nowf, que1[tail1].pos = j, tail1++;
                dp[i][j] = max(dp[i][j], que1[head1].f - j * BP[i]);
            }
        }
        //
        int ans = 0;
        for(int i = 0; i <= MaxP; i++){
            ans = max(ans, dp[n][i]);
        }
        cout << ans << endl;
    }
    return 0;
}