uva 12654

dp,用优先队列存,上个节点节点覆盖下来的长度;

不过还不是很明白;

 #include<cstdio>
#include<queue>
#include<algorithm>
#define maxn 1005
#define inf 999999
using namespace std;
struct node
{
int id;
int v;
node(int id=,int v=):id(id),v(v){}
bool operator<(const node &t)const
{
return v>t.v;
}
};
priority_queue<node>q1,q2; int f[maxn],a[maxn];
int main()
{
int n,c,t1,t2,x;
while(scanf("%d%d%d%d",&n,&c,&t1,&t2)!=EOF)
{
while(!q1.empty())q1.pop();
while(!q2.empty())q2.pop();
q1.push(node(,));
q2.push(node(,));
for(int i=;i<=n;i++)scanf("%d",&a[i]);
for(int i=;i<=n;i++)
{
while(!q1.empty()&&a[q1.top().id+]+t1<a[i])q1.pop();
while(!q2.empty()&&a[q2.top().id+]+t2<a[i])q2.pop();
f[i]=inf;
if(!q1.empty())f[i]=min(f[i],q1.top().v+t1);
if(!q2.empty())f[i]=min(f[i],q2.top().v+t2);
q1.push(node(i,f[i]));
q2.push(node(i,f[i]));
// printf("%d\n",f[i]);
}
printf("%d\n",f[n]);
}
return ;
}
上一篇:android推送-PHP(第三方推送:个推)


下一篇:Spring整合JMS(一)——基于ActiveMQ实现 (转)