单调队列优化DP，多重背包

时间：2021-03-04 08:42:21

单调队列优化DP：http://www.cnblogs.com/ka200812/archive/2012/07/11/2585950.html

单调队列优化多重背包：http://blog.csdn.net/flyinghearts/article/details/5898183

传送门：hdu 3401 Trade

/**************************************************************

    Problem:hdu 3401 Trade

    User: youmi

    Language: C++

    Result: Accepted

    Time:171MS

    Memory:17368K

****************************************************************/

//#pragma comment(linker, "/STACK:1024000000,1024000000")

//#include<bits/stdc++.h>

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <map>

#include <stack>

#include <set>

#include <sstream>

#include <cmath>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#define zeros(a) memset(a,0,sizeof(a))

#define ones(a) memset(a,-1,sizeof(a))

#define sc(a) scanf("%d",&a)

#define sc2(a,b) scanf("%d%d",&a,&b)

#define sc3(a,b,c) scanf("%d%d%d",&a,&b,&c)

#define scs(a) scanf("%s",a)

#define sclld(a) scanf("%I64d",&a)

#define pt(a) printf("%d\n",a)

#define ptlld(a) printf("%I64d\n",a)

#define rep(i,from,to) for(int i=from;i<=to;i++)

#define irep(i,to,from) for(int i=to;i>=from;i--)

#define Max(a,b) ((a)>(b)?(a):(b))

#define Min(a,b) ((a)<(b)?(a):(b))

#define lson (step<<1)

#define rson (lson+1)

#define eps 1e-6

#define oo 1e9

#define TEST cout<<"*************************"<<endl

const double pi=*atan(1.0);

using namespace std;

typedef long long ll;

template <class T> inline void read(T &n)

{

    char c; int flag = ;

    for (c = getchar(); !(c >= '' && c <= '' || c == '-'); c = getchar()); if (c == '-') flag = -, n = ; else n = c - '';

    for (c = getchar(); c >= '' && c <= ''; c = getchar()) n = n *  + c - ''; n *= flag;

}

ll Pow(ll base, ll n, ll mo)

{

    ll res=;

    while(n)

    {

        if(n&)

            res=res*base%mo;

        n>>=;

        base=base*base%mo;

    }

    return res;

}

//***************************

int T,P,w;

const int maxn=+;

const ll mod=;

int dp[maxn][maxn];

int ap[maxn],bp[maxn];

int as[maxn],bs[maxn];

struct node

{

    int val,p;

};

node q[maxn];

int head,tail;

int main()

{

    #ifndef ONLINE_JUDGE

    freopen("in.txt","r",stdin);

    #endif

    int T_T;

    scanf("%d",&T_T);

    for(int kase=;kase<=T_T;kase++)

    {

        sc3(T,P,w);

        rep(i,,T)

        {

            sc2(ap[i],bp[i]);//buy,sell,money

            sc2(as[i],bs[i]);//buy,sell,number

        }

        rep(i,,T)

            rep(j,,P)

                dp[i][j]=-oo;

        dp[][]=;

        rep(i,,T)

        {

            if(i<=w+)

            {

                rep(j,,min(P,as[i]))

                    dp[i][j]=-ap[i]*j;

            }

            rep(j,,P)

                dp[i][j]=max(dp[i][j],dp[i-][j]);

            if(i<=w+)

                continue;

            head=tail=;

            for(int j=P;j>=;j--)

            {

                int temp=dp[i-w-][j]+bp[i]*j;

                while(tail>head&&temp>q[tail-].val) tail--;

                q[tail].val=temp,q[tail].p=j,tail++;

                while(tail>head&&q[head].p-bs[i]>j)  head++;

                temp=q[head].val;

                dp[i][j]=max(dp[i][j],temp-bp[i]*j);

            }

            tail=head=;

            rep(j,,P)

            {

                int temp=dp[i-w-][j]+ap[i]*j;

                while(tail>head&&temp>q[tail-].val)  tail--;

                q[tail].val=temp,q[tail].p=j,tail++;

                while(tail>head&&q[head].p+as[i]<j) head++;

                temp=q[head].val;

                dp[i][j]=max(dp[i][j],temp-ap[i]*j);

            }

        }

        int ans=;

        rep(i,,P)

            ans=max(ans,dp[T][i]);

        pt(ans);

    }

    return ;

}

相关文章