单调队列优化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 ",a) #define ptlld(a) printf("%I64d ",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=4*atan(1.0); using namespace std; typedef long long ll; template <class T> inline void read(T &n) { char c; int flag = 1; for (c = getchar(); !(c >= '0' && c <= '9' || c == '-'); c = getchar()); if (c == '-') flag = -1, n = 0; else n = c - '0'; for (c = getchar(); c >= '0' && c <= '9'; c = getchar()) n = n * 10 + c - '0'; n *= flag; } ll Pow(ll base, ll n, ll mo) { ll res=1; while(n) { if(n&1) res=res*base%mo; n>>=1; base=base*base%mo; } return res; } //*************************** int T,P,w; const int maxn=2000+10; const ll mod=1000000007; 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=1;kase<=T_T;kase++) { sc3(T,P,w); rep(i,1,T) { sc2(ap[i],bp[i]);//buy,sell,money sc2(as[i],bs[i]);//buy,sell,number } rep(i,0,T) rep(j,0,P) dp[i][j]=-oo; dp[0][0]=0; rep(i,1,T) { if(i<=w+1) { rep(j,0,min(P,as[i])) dp[i][j]=-ap[i]*j; } rep(j,0,P) dp[i][j]=max(dp[i][j],dp[i-1][j]); if(i<=w+1) continue; head=tail=0; for(int j=P;j>=0;j--) { int temp=dp[i-w-1][j]+bp[i]*j; while(tail>head&&temp>q[tail-1].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=0; rep(j,0,P) { int temp=dp[i-w-1][j]+ap[i]*j; while(tail>head&&temp>q[tail-1].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=0; rep(i,0,P) ans=max(ans,dp[T][i]); pt(ans); } return 0; }