misschuer

常用链接

统计

积分与排名

百事通

最新评论

poj 2393 Yogurt factory

//用单调队列优化
#include <iostream>
#define MAXV 10001
using namespace std;

typedef 
struct {

    __int64 val;
    
int in;
}point;

point q[MAXV];
__int64 staf[MAXV];
__int64 cost[MAXV];
__int64 dp[MAXV], n;
__int64 c;

void res() {

    
int s = 0, e = -1;
    dp[ 
0 ] = 0;
    point p, pt;

    
for(int i = 1; i <= n; ++ i) {
    
        p.
in = i;
        p.val 
= cost[ i ];

        
while(s <= e) {
        
            pt 
= q[ e ];

            
if(pt.val + c * (i - pt.in< p.val) break;
                
            e 
--;
        }
        
        
++ e;        q[ e ] = p;          pt = q[ s ];
        dp[ i ] 
=  dp[i - 1+ staf[ i ] * (pt.val + c * (i - pt.in));
    }

    printf(
"%I64d\n", dp[ n ]);
}

int main() {

    
while(~scanf("%d %I64d"&n, &c)) {
    
        
for(int i = 1; i <= n; ++ i)
            scanf(
"%I64d %I64d"&cost[ i ], &staf[ i ]);

        res();
    }
    
return 0;
}

posted on 2011-03-27 20:22 此最相思 阅读(239) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理