首页 > 代码库 > hdu3401：单调队列优化dp
hdu3401：单调队列优化dp
第一个单调队列优化dp
写了半天，最后初始化搞错了还一直wa。。
题目大意：
炒股，总共 t 天，每天可以买入na[i]股，卖出nb[i]股，价钱分别为pa[i]和pb[i]，最大同时拥有p股
且一次交易后至少要间隔w天才能再次交易，初始有0股，本金无限，求最大收益
题解：
dp[i][j]表示第 i 天，有 j 股的最大收益
状态转移 dp[i][j]=max{dp[i-1][j](不买不卖)，dp[r][k]-(j-k)*pa[i]（i-r>w,j-k<=na[i]，买），dp[r][k]+(k-j)*pb[i]（i-r>w,k-j<=nb[i]，卖）}
复杂度 为 t*t*p*p
首先我们可以看出 dp[i][j]>=dp[i-1][j]（不买不卖转移）
所以可以将 r 确定为 i-w-1，复杂度变为t*p*p 还是很大
然后对于买，移项有
dp[i][j]+j*pa[i]=dp[r][k]+k*pa[i]。右边与 j无关， 可见我们只需要对每一个 i 维护一个关于k的单调队列，就可以在 p时间内求出所有的dp[i][j]
复杂度降为 t*p 可以接受了
最后注意下边界条件：
1到w+1的都是从初始条件下转移的
代码：
#include <iostream>#include <stdio.h>#include<string.h>#include<algorithm>#include<string>#include<ctype.h>using namespace std;#define MAXN 2000#define inf 200000000int na[MAXN+10],nb[MAXN+10],pa[MAXN+10],pb[MAXN+10];int dp[MAXN+10][MAXN+10];int t,p,w;typedef struct Node{ int val,num;}node;typedef struct dqueue{ node q[MAXN*100]; int l,r; bool empty() { return l==r; } void clear() { l=0;r=0; } node front() { return q[l]; } void pop() { l++; } void push(node x) { if(l==r) { q[r++]=x; return; } if(x.val>q[l].val) { r=l; q[r++]=x; return; } for(int i=r;i>l;i--) { if(x.val<q[i-1].val) { r=i; break; } } q[r++]=x; }}Dqueue;Dqueue qa,qb;int buy(int now,int n){ node tmp; while(1) { tmp=qa.front(); if(tmp.num<n-na[now]) { qa.pop(); } else break; } return tmp.val;}int sale(int now,int n){ node tmp; while(1) { tmp=qb.front(); if(tmp.num<n) { qb.pop(); } else break; } return tmp.val;}void DP(){ for(int i=0;i<=t;i++) { for(int j=0;j<=p;j++) { dp[i][j]=-inf; } } node no; for(int i=1;i<=w+1;i++) { for(int j=0;j<=na[i];j++) { dp[i][j]=-pa[i]*j; } for(int j=0;j<=p;j++) { dp[i][j]=max(dp[i][j],dp[i-1][j]); } } for(int i=w+2;i<=t;i++) { qa.clear(); qb.clear(); int r=i-w-1; //上一次交易的天数 for(int j=0;j<nb[i];j++) { no.num=j; no.val=dp[r][j]+j*pb[i]; qb.push(no); } for(int j=0;j<=p;j++) { no.num=j; no.val=dp[r][j]+j*pa[i]; qa.push(no); if(j+nb[i]<=p) { no.num=j+nb[i]; no.val=dp[r][j+nb[i]]+(j+nb[i])*pb[i]; qb.push(no); } dp[i][j]=max(dp[i][j],dp[i-1][j]); //不买 int tmp=buy(i,j); dp[i][j]=max(dp[i][j],tmp-j*pa[i]); //买 tmp=sale(i,j); dp[i][j]=max(dp[i][j],tmp-j*pb[i]); //卖 } }}int main(){ int T; scanf("%d",&T); while(T--) { scanf("%d%d%d",&t,&p,&w); for(int i=1;i<=t;i++) { scanf("%d%d%d%d",pa+i,pb+i,na+i,nb+i); } DP(); int ans=0; for(int i=0;i<=p;i++) { ans=max(ans,dp[t][i]); } printf("%d\n",ans); } return 0;}
hdu3401：单调队列优化dp
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。