首页 > ACM题库 > HDU-杭电 > HDU 3401-Trade-动态规划-[解题报告]HOJ
2014
03-23

HDU 3401-Trade-动态规划-[解题报告]HOJ

Trade

问题描述 :

Recently, lxhgww is addicted to stock, he finds some regular patterns after a few days’ study.
He forecasts the next T days’ stock market. On the i’th day, you can buy one stock with the price APi or sell one stock to get BPi.
There are some other limits, one can buy at most ASi stocks on the i’th day and at most sell BSi stocks.
Two trading days should have a interval of more than W days. That is to say, suppose you traded (any buy or sell stocks is regarded as a trade)on the i’th day, the next trading day must be on the (i+W+1)th day or later.
What’s more, one can own no more than MaxP stocks at any time.

Before the first day, lxhgww already has infinitely money but no stocks, of course he wants to earn as much money as possible from the stock market. So the question comes, how much at most can he earn?

输入:

The first line is an integer t, the case number.
The first line of each case are three integers T , MaxP , W .
(0 <= W < T <= 2000, 1 <= MaxP <= 2000) .
The next T lines each has four integers APi,BPi,ASi,BSi( 1<=BPi<=APi<=1000,1<=ASi,BSi<=MaxP), which are mentioned above.

输出:

The first line is an integer t, the case number.
The first line of each case are three integers T , MaxP , W .
(0 <= W < T <= 2000, 1 <= MaxP <= 2000) .
The next T lines each has four integers APi,BPi,ASi,BSi( 1<=BPi<=APi<=1000,1<=ASi,BSi<=MaxP), which are mentioned above.

样例输入:

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

/*
状态转移方程为:
买入:
  dp[i][j]=max(dp[r][k]-(j-k)*ap[i]);(0<j-k<=bnum[i])
卖出:
  dp[i][j]=max(dp[r][k]+(k-j)*bp[i]);(0<k-j<=snum[i])
不买不卖:
  dp[i][j]=max(dp[i][j],dp[i-1][j]);
很明显时间复杂度为o(maxp^2*t^2) 超时!!
考虑怎么优化:
  dp[i][j]+j*ap[i]=max(dp[r][k]+k*bp[i]);
同理:
  dp[i][j]+j*bp[i]=max(dp[r][k]+k*ap[i]);

 令f(k)=dp[i][k]+k*AP[i]
 f(j)=max(f(k)) (j-AS[i]<=k<=j)//经典单调队列
 所以dp[i][j]=f(j)-j*AP[i]
 卖
 令ff(k)=dp[i][k]+k*AP[i]
 ff(j)=max(ff(k)) (j<=k<=j+BS[i])
 所以dp[i][j]=ff(j)-j*BP[i]

 */

/*
状态转移方程为:
买入:
  dp[i][j]=max(dp[r][k]-(j-k)*ap[i]);(0<j-k<=bnum[i])
卖出:
  dp[i][j]=max(dp[r][k]+(k-j)*bp[i]);(0<k-j<=snum[i])
不买不卖:
  dp[i][j]=max(dp[i][j],dp[i-1][j]);
很明显时间复杂度为o(maxp^2*t^2) 超时!!
考虑怎么优化:
  dp[i][j]+j*ap[i]=max(dp[r][k]+k*bp[i]);
同理:
  dp[i][j]+j*bp[i]=max(dp[r][k]+k*ap[i]);
买
 令f(k)=dp[i][k]+k*AP[i]
 f(j)=max(f(k)) (j-AS[i]<=k<=j)//经典单调队列
 所以dp[i][j]=f(j)-j*AP[i]
 卖
 令ff(k)=dp[i][k]+k*AP[i]
 ff(j)=max(ff(k)) (j<=k<=j+BS[i])
 所以dp[i][j]=ff(j)-j*BP[i]
 */
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<memory.h>
#include<cmath>
using namespace std;
const int maxn=2002;
const int maxm=2002;
const int inf=1<<29;
int q[maxn];
int t,cas,maxp,w,ap[maxn],bp[maxn],as[maxn],bs[maxn];
int dp[maxn][maxm];
int main()
{
    scanf("%d",&cas);
    while(cas--)
    {
        int i,j;
        scanf("%d%d%d",&t,&maxp,&w);
        for(i=1; i<=t; i++)
        {
            scanf("%d%d%d%d",&ap[i],&bp[i],&as[i],&bs[i]);
        }
        for(i=0; i<=t; i++)
        {
            for(j=0; j<=maxp; j++)
            {
                dp[i][j]=-inf;
            }
        }
        dp[0][0]=0;
        for (i=1; i<=w+1; i++)//前w天买第一批货物
        {
            for (j=0; j<=min(as[i],maxp); j++) dp[i][j]=-ap[i]*j;
        }
        for(i=1; i<=t; i++)
        {
            for(j=0; j<=maxp; j++) //不买不卖
            {
                dp[i][j]=max(dp[i][j],dp[i-1][j]);
            }
            if(i<=w+1) continue;//第1天有交易也要第w+2后才能再次交易
            int pre=i-w-1;
            //买
            int front = 1;
            int tail = 0;
            for (j = 0; j <= maxp; ++j)
            {
                while (tail >= front && q[front] + as[i] < j) front++;//单调队列维护长度不能超过as
                int tmp = dp[i - w - 1][j];
                while (tail >= front && dp[pre][q[tail]] - ap[i]*(j - q[tail]) < tmp) tail--;
                q[++tail] = j;
                if (tail >= front) dp[i][j] = max(dp[i][j],dp[pre][q[front]] - ap[i]*(j - q[front]));
            }
            //卖
            front = 1;
            tail = 0;
            for (j = maxp; j >= 0; --j)
            {
                while (tail >= front && q[front] - bs[i] > j) front++;
                int tmp = dp[i - w - 1][j];
                while (tail >= front && dp[pre][q[tail]] + bp[i]*(q[tail] - j) < tmp) tail--;
                q[++tail] = j;
                if (tail >= front) dp[i][j] = max(dp[i][j],dp[pre][q[front]] + bp[i]*(q[front] - j));
            }
        }
        int ans=0;
        for(i=0; i<=maxp; i++)
        {
            ans=max(ans,dp[t][i]);
        }
        cout<<ans<<endl;
    }
    return 0;
}

参考:http://blog.csdn.net/azheng51714/article/details/7951436


  1. 很高兴你会喜欢这个网站。目前还没有一个开发团队,网站是我一个人在维护,都是用的开源系统,也没有太多需要开发的部分,主要是内容整理。非常感谢你的关注。

  2. 这道题这里的解法最坏情况似乎应该是指数的。回溯的时候
    O(n) = O(n-1) + O(n-2) + ….
    O(n-1) = O(n-2) + O(n-3)+ …
    O(n) – O(n-1) = O(n-1)
    O(n) = 2O(n-1)