hdu 单调队列

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4122

代码:

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<string>
using namespace std; const int maxn = ; struct Node
{
int id,val;
}; int order[];
long long R[];
int S,T,N,M; struct Myqueue
{
Node Q[maxn];
int head,tail; void init()
{
head = tail = ;
} void push(int id,int val)
{
while(head < tail && Q[tail-].val+S*(id-Q[tail-].id) >= val)
tail--;
Q[tail].val = val;
Q[tail++].id = id;
} void pop(int id)
{
while(head < tail && Q[head].id < id - T) //单调区间的最小值。
head++;
} Node getfront()
{
return Q[head];
}
}solver; map<string,int> mymap; void init()
{
mymap["Jan"] = ; mymap["Feb"] = ; mymap["Mar"] = ;
mymap["Apr"] = ; mymap["May"] = ; mymap["Jun"] = ;
mymap["Jul"] = ; mymap["Aug"] = ; mymap["Sep"] = ;
mymap["Oct"] = ; mymap["Nov"] = ; mymap["Dec"] = ;
} int mou[] = {,,,,,,,,,,,,};
void GetOrder()
{
string s;
int date,year,H; for(int i=; i<=N; i++)
{
cin>>s;
scanf("%d %d %d %I64d",&date,&year,&H,&R[i]);
int mouth = mymap[s];
year -= ;
order[i] = (*+)*(year/);
year = year%;
if(year == )
{
for(int j=; j<mouth; j++)
{
order[i] += mou[j];
if(j == ) order[i] += ;
}
}
else
{
order[i] += + (year-)*;
for(int j=; j<mouth; j++)
order[i] += mou[j];
}
order[i] += date - ;
order[i] = order[i]* + H + ;
}
}
int main()
{
//freopen("E:\\acm\\input.txt","r",stdin);
init();
while(cin>>N>>M && N+M)
{
GetOrder(); scanf("%d %d",&T,&S);
solver.init(); int cnt = ;
long long ans = ;
for(int i=; i<=M; i++)
{
int cost;
scanf("%d",&cost); solver.push(i,cost);
solver.pop(i); //先去掉过期的 Node cur = solver.getfront();
while(order[cnt] == i && cnt <= N) //cnt的上限,和while循环,考虑了,为啥不加。
{
ans += (cur.val + (i-cur.id)*S ) * R[cnt]; //乘法溢出问题
cnt ++;
}
}
printf("%I64d\n",ans);
}
}
上一篇:ubuntu pycharm 无法 lock from launcher 问题解决


下一篇:Angularjs 2 绝对零基础的教程(1):从安装配置开始