hdu 3401 Trade(单调队列优化dp)

hdu 3401 Trade(单调队列优化dp)


题意：lxhgww喜欢炒股票，他可以在第i天买入或者卖出若干张股票（一天只能买或者卖），两个交易日之间至少相隔w天，问他t天后最多能赚多少。


解题思路：首先我们可以得出的dp状态是，dp[i][j]表示第i天有j张股票，最多能持有多少钱，初始值dp[0][0] = 0 ， 其余都为-INF。那么我们可以得到一个时间复杂度为o(t*mxp*交易上限)的暴力转移方程，这样还是会超时。找单调性，对于买入股票（卖出跟买入差不多的），设上一次能转移过来的交易日为k（ if ( i <= w )  k = 0 ; else k =i-w-1 ;)，而j张股票的最优值是从i推过来的，那么j+1的最优值至少是从i推过来的，这个性质我是这样推出来的:


若dp[k][i] - (j-i) * x (x表示当天的买入单价)>dp[k][i-1] - (j-(i-1)) *ｘ，则dp[k][i] - (j+1-i) * x > dp[k][i-1] - (j+1-(i-1)) * x。这样就有单调性了，那么就可以用单调队列优化了。




[cpp] view plaincopyprint?
#include  
#include  
#include  
using namespace std ;  
  
const int INF = -10000000 ;  
const int maxn = 2222 ;  
int w , t , mxp ;  
struct Deque {  
    int val[maxn] , pos[maxn] ;  
    int tail , star ;  
    void init () {  
        star = 1 , tail = 0 ;  
    }  
    int empty () {  
        return star > tail ;  
    }  
    void push ( int id , int v ) {  
        while ( !empty () && val[tail] < v ) tail -- ;  
        val[++tail] = v ;  
        pos[tail] = id ;  
    }  
    int get ( int p , int k , int flag ) {  
        if ( !flag ) {  
            while ( pos[star] < p - k ) star ++ ;  
            return pos[star] ;  
        }  
        else {  
            while ( pos[star] > p + k ) star ++ ;  
            return pos[star] ;  
        }  
    }  
} q ;  
  
int dp[maxn][maxn] ;  
int a[maxn] , b[maxn] , c[maxn] , d[maxn] ;  
  
int main () {  
    int cas ;  
    scanf ( "%d" , &cas ) ;  
    while ( cas -- ){  
        int i , j , k ;  
        scanf ( "%d%d%d" , &t , &mxp , &w ) ;  
        for ( i = 1 ; i <= t ; i ++ )  
            scanf ( "%d%d%d%d" , &a[i] , &b[i] , &c[i] , &d[i] ) ;  
        for ( i = 0 ; i <= t ; i ++ )  
            for ( j = 0 ; j <= mxp ; j ++ )  
                dp[i][j] = INF ;  
        dp[0][0] = 0 ;  
        for ( i = 1 ; i <= t ; i ++ ) {  
            for ( j = 0 ; j <= mxp ; j ++ )  
                dp[i][j] = dp[i-1][j] ;  
            q.init () ;  
            if ( i <= w ) k = 0 ;  
            else k = i - w - 1 ;  
            for ( j = 0 ; j <= mxp ; j ++ ) {  
                q.push ( j , dp[k][j] + j * a[i] ) ;  
                int id = q.get ( j , c[i] , 0 ) ;  
                dp[i][j] = max ( dp[i][j] , dp[k][id] - (j-id) * a[i] ) ;  
            }  
            q.init () ;  
            for ( j = mxp ; j >= 0 ; j -- ) {  
                q.push ( j , dp[k][j] + j * b[i] ) ;  
                int id = q.get ( j , d[i] , 1 ) ;  
                dp[i][j] = max ( dp[i][j] , dp[k][id] + (id-j) * b[i] ) ;  
            }  
        }  
        int ans = 0 ;  
        for ( i = 0 ; i <= mxp ; i ++ ) ans = max ( ans , dp[t][i] ) ;  
        printf ( "%d\n" , ans ) ;  
    }  
    return 0 ;  
}