#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <limits>
#include <string>
#include <sstream>
using namespace std;

const int oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f;

int n,a,b;
double len[3+1];
double cost[3+1];
double d[10000+1];
double f[10000+1];

int main()
{
    while (~scanf("%lf%lf%lf%lf%lf%lf%d%d%d",&len[1],&len[2],&len[3],&cost[1],&cost[2],&cost[3],&n,&a,&b))
    {
        memset(d,0,sizeof(d));
        for (int i=2;i<=n;i++)
            scanf("%lf",&d[i]);
        for (int i=1;i<=n;i++)
            f[i]=(numeric_limits<double>::max)()/2;
        f[a]=0;
        for (int i=a;i<=b;i++)
            for (int j=i-1;j>=a;j--)
                for (int k=1;k<=3;k++)
                    if (d[i]-d[j]<=len[k])
                    {
                        f[i]=min(f[i],f[j]+cost[k]);
                        break;
                    }
        printf("%.0lf\n",f[b]);
    }
}

***看了各种题解把我吓坏了 神马 单调队列。二分。。后来才知道只是一个简单的动规。。。而且可以秒过
不过。。要注意:
1.数组初值开到maxlongint..
2.是表示距离的数组s[i]从2开始赋值
3.两个车站之间的距离必须小于等于l3才可以直达

..***.测试数据 #0: Accepted, time = 0 ms, mem = 1596 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 1596 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 1596 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 1596 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 1596 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 1592 KiB, score = 10
测试数据 #6: Accepted, time = 15 ms, mem = 1592 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 1596 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 1596 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 1596 KiB, score = 10
```Accepted, time = 15 ms, mem = 1596 KiB, score = 100****

var l,c:array[1..3]of longint;
s,f:array[0..100000]of longint;
a,b,n,i,j,x,m:longint;

function min(x,y:longint):longint;
begin
if x>y then exit(y) else exit(x);
end;

begin
for i:=1 to 3 do read(l[i]);
for i:=1 to 3 do read(c[i]);
readln;
readln(n);
readln(a,b);
for i:=1 to n do f[i]:=maxlongint ;
f[a]:=0;
s[1]:=0;
for i:=2 to n do readln(s[i]);
for i:=a+1 to b do
for j:=i-1 downto a do
begin
x:=s[i]-s[j];
if x<=l[1] then m:=c[1] else
if x<=l[2] then m:=c[2] else
if x<=l[3] then m:=c[3] else break;
f[i]:=min(f[i],f[j]+m);
end;
writeln(f[b]);
end.```

这个题目如果用普通的DP虽然可以AC,但是一旦火车站的数量N过大时,普通DP是无法解决的,如果用的是java语言必定超时,
这里要用单调队列DP,而且是三重一维单调DP(三重对应于:L1,L2,L3).
java代码如下:
import java.util.Scanner;
public class Main {

private static int L1,L2,L3,C1,C2,C3;
private static int N,start,end;
private static int[] d;
private static int[] queue1;//对应L1;索引对应的值:单调递增的队列
private static int[] queue2;//对应L2
private static int[] queue3;//对应L3
private static int head1,rail1,head2,rail2,head3,rail3;
private static int[] DP;
private static int max=1499999999;
public static void main(String[] args){
Scanner in = new Scanner(System.in);
L1 = in.nextInt();
L2 = in.nextInt();
L3 = in.nextInt();
C1 = in.nextInt();
C2 = in.nextInt();
C3 = in.nextInt();
N = in.nextInt();
start = in.nextInt();
end = in.nextInt();

d = new int[N+1];
queue1 = new int[N+1];
queue2 = new int[N+1];
queue3 = new int[N+1];
DP = new int[N+1];
DP[0] = max;
DP[start] = 0;
head3=head2=head1=1;
rail3=rail2=rail1=2;
queue1[head1]=queue2[head2]=queue3[head3]=start;
for(int index=2;index<=N;index++)
d[index] = in.nextInt();
resolve();
System.out.print(DP[end]);
in.close();
}

private static void resolve(){
int index1,index2,index3;
for(int i=start+1;i<=end;i++){
index1 = getIndex(i,1);
index2 = getIndex(i,2);
index3 = getIndex(i,3);
//if(d[i]-d[index]<=L3)
DP[i] = min(DP[index3]+C3,min(DP[index2]+C2,DP[index1]+C1));
push_back(i);
}
}

private static void push_back(int index){
while(head1 < rail1&&DP[queue1[rail1-1]] > DP[index])
rail1--;
queue1[rail1++] = index;
while(head2 < rail2&&DP[queue2[rail2-1]] > DP[index])
rail2--;
queue2[rail2++] = index;
while(head3 < rail3&&DP[queue3[rail3-1]] > DP[index])
rail3--;
queue3[rail3++] = index;
}

private static int getIndex(int index,int sign){
if(sign == 1){
while(head1 < rail1&&d[index]-d[queue1[head1]] > L1)
head1++;
if(head1 == rail1&&d[index]-d[queue1[head1]] > L1)
return 0;
return queue1[head1];
}
else if(sign == 2){
while(head2 < rail2&&d[index]-d[queue2[head2]] > L2)
head2++;
if(head2 == rail2&&d[index]-d[queue2[head2]] > L2)
return 0;
return queue2[head2];
}
else {
while(head3 < rail3&&d[index]-d[queue3[head3]] > L3)
head3++;
if(head3 == rail3&&d[index]-d[queue3[head3]] > L3)
return 0;
return queue3[head3];
}
}

private static int getFee(int l){
if(l>0&&l<=L1)return C1;
else if(l>L1&&l<=L2)return C2;
else if(l>L2&&l<=L3)return C3;
return 0;
}

private static int min(int a,int b){
if(a < b)return a;
else return b;
}

}
大家都知道java的速度比C语言慢许多,所以用java解题可以看出高效算法和普通算法之间时间效率的差别(当大家看到java代码的运行时间时,不要吃惊,因为java确实太慢。。。)

program asdfasf;
var n,m,i,j,k,l1,x,y,z,l2,l3,c1,c2,c3,dx,dy,l:longint;
a,b,c,d,f:array[0..100000]of longint;
function min(a,b:longint):longint;
begin
if a>b then exit(b) else exit(a);
end;
begin

fillchar(f,sizeof(f),$7f);
readln(l1,l2,l3,c1,c2,c3);
readln(n);
readln(dx,dy);
if dx>dy then begin
l:=dx; dx:=dy; dy:=l;
end;
for i:=2 to n do
readln(a[i]);
a[1]:=0;
f[dx]:=0;
for i:=dx+1 to n do
for j:=dx to i do
begin
x:=a[i]-a[j];
if x<=l1 then f[i]:=min(f[i],f[j]+c1);
if (x>=l1)and(x<=l2) then f[i]:=min(f[i],f[j]+c2);
if (x>=l2)and(x<=l3) then f[i]:=min(f[i],f[j]+c3);
end;
writeln(f[dy]);
end.

var
a,f:array[1..10000]of longint;
l1,l2,l3,c1,c2,c3,n,g,h,i,j:longint;
function jia(x:longint):longint;
begin
if x<=l1 then exit(c1);
if x<=l2 then exit(c2);exit(c3);
end;
function min(x,y:longint):longint;
begin
if x<y then exit(x);exit(y);
end;
begin
read(l1,l2,l3,c1,c2,c3,n,h,g);
for i:=2 to n do read(a[i]);
for i:=h+1 to g do f[i]:=maxlongint;
for i:=h+1 to g do
for j:=h to i-1 do
if a[i]-a[j]<=l3 then
f[i]:=min(f[i],f[j]+jia(a[i]-a[j]));
writeln(f[g]);
end.

AC99 纪念

#include <stdio.h>
#define MAX 2000000000
int distance[20000];
int dp[20000];
int main(){
int L1,L2,L3,C1,C2,C3;
int num,terminalA,terminalB;
int i,k,dist;
scanf("%d%d%d%d%d%d",&L1,&L2,&L3,&C1,&C2,&C3);
scanf("%d%d%d",&num,&terminalA,&terminalB);
for(i=0;i<num-1;i++)
scanf("%d",&distance[i+2]);
for(i=0;i<=num+5;i++)
dp[i]=MAX;
dp[terminalA]=0;
for(i=terminalA;i<=terminalB;i++){
for(k=terminalA;k<i;k++){
dist=distance[i]-distance[k];
if(dist<=L1){
if(dp[i]>dp[k]+C1)
dp[i]=dp[k]+C1;
}else if(dist<=L2){
if(dp[i]>dp[k]+C2)
dp[i]=dp[k]+C2;
}else if(dist<=L3){
if(dp[i]>dp[k]+C3)
dp[i]=dp[k]+C3;
}
}
}
printf("%d\n",dp[terminalB]);
return 0;
}

大家不要学我，第一次f【i】=1千万 10分
第二次 10亿 80分
第三次 maxlongint ac
QAQ

var
a,f:array[1..10000]of longint;
l1,l2,l3,c1,c2,c3,n,g,h,i,j:longint;
function jia(x:longint):longint;
begin
if x<=l1 then exit(c1);
if x<=l2 then exit(c2);exit(c3);
end;
function min(x,y:longint):longint;
begin
if x<y then exit(x);exit(y);
end;
begin
read(l1,l2,l3,c1,c2,c3,n,h,g);
for i:=2 to n do read(a[i]);
for i:=h+1 to g do f[i]:=maxlongint;
for i:=h+1 to g do
for j:=h to i-1 do
if a[i]-a[j]<=l3 then
f[i]:=min(f[i],f[j]+jia(a[i]-a[j]));
writeln(f[g]);
end.

为啥从后向前推就一个点也过不去啊
代码如下：
for (int i=B-1;i>=A;--i)
{
min=1300000001;

for (int j=i+1;j<=B && d[j]-d[i]<=l3 ;++j)
if (f[j]+d[j]-d[i]<min)
{

min=f[j]+price(d[j]-d[i]);

}
f[i]=min;

// printf("%d %d\n",i,min);
}*/

测试数据 #0: Accepted, time = 0 ms, mem = 888 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 896 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 892 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 888 KiB, score = 10
测试数据 #4: Accepted, time = 43 ms, mem = 892 KiB, score = 10
测试数据 #5: Accepted, time = 78 ms, mem = 892 KiB, score = 10
测试数据 #6: Accepted, time = 62 ms, mem = 888 KiB, score = 10
测试数据 #7: Accepted, time = 131 ms, mem = 892 KiB, score = 10
测试数据 #8: Accepted, time = 156 ms, mem = 892 KiB, score = 10
测试数据 #9: Accepted, time = 162 ms, mem = 888 KiB, score = 10

var f,h:array[0..10001] of int64;
l1,l2,l3,c1,c2,c3,i,j,n,a,b,x:longint;
function min(x,y:int64):int64;
begin
if x>y then exit(y) else exit(x);
end;
function dist(x,y:int64):int64;
var t,p:int64;
begin
t:=h[y]-h[x];
if t<=l1 then exit(c1);
if (t>l1) and (t<=l2) then exit(c2);
exit(c3);
end;
begin
readln(l1,l2,l3,c1,c2,c3);
fillchar(f,sizeof(f),60);
fillchar(h,sizeof(h),0);
readln(n);readln(a,b);
i:=1;
while i<>a do begin readln(h[1]);inc(i);end;
n:=1;
repeat
inc(n);
readln(x);
h[n]:=x-h[1];
until n=b-a+1;
f[1]:=0;
for i:=2 to n do
for j:=1 to i-1 do
if h[i]-h[j]<=l3 then
f[i]:=min(f[i],f[j]+dist(j,i));
writeln(f[n]);
end.

请问各位大牛，如何才能秒杀？时间太长了啊

弱弱的问一句，难道这是单调DP？为什么感觉很水

f[i] : i与较小端的费用
xi(a,b) : a,b之间的费用
f[i] = min(f[i],f[j]+xi(i,j)),j<i,且j.i距离不超过s3

program p1292;
var
i,j,k,l,n,min,m,pop,ans,w1,w2:longint;
l1,l2,l3,c1,c2,c3:longint;
a,f:array[0..10005]of longint;
function fee(a1,b:longint):longint;
begin
if( 0 < (a[b]-a[a1]))and ((a[b]-a[a1])<= l1) then exit(c1);
if( l1 < (a[b]-a[a1]))and( (a[b]-a[a1])<= l2) then exit(c2);
if( l2 < (a[b]-a[a1]))and( (a[b]-a[a1])<= l3) then exit(c3);
end;
begin
read(l1,l2,l3,c1,c2,c3); readln(n); readln(w1,w2);
for i:=2 to (n) do readln(a[i]);
for i:=(w1+1) to w2 do
begin
min:=maxlongint;
for j:=(i-1) downto w1 do
begin
if (a[i]-a[j])>l3 then break;
if min>f[j]+fee(j,i) then min:=f[j]+fee(j,i);
end;
f[i]:=min;
end;
writeln(f[w2]);
end.

f[i]表示到达I的最少费用

f[i]=f[j1]+c1 f[j2]+c2 f[j3]+c3 分别要满足可以到达

用三个单调队列维护就行

这方法是不是有点垃圾？

N才1万有点弱

初始值注意了 会超过maxlongint>>1 所以还是赋初值为maxlongint

简单DP ！！！maxn=1300000001！！！

要不会不过

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

const max=100000;

type fromlist=array[1..max] of integer;

list=array[1..max] of longint;

var c1,c2,c3,l1,l2,l3,c : longint;

n,f,t,i : integer;

dist,cost : list;

from1,from2,from3 : fromlist;

procedure getfrom(var from : fromlist; l1 : longint);

var i,j : integer;

begin

fillchar(from,sizeof(from),0);

j := n;

for i := n downto f + 1 do

begin

repeat dec(j)

until (j < f) or (dist[i] - dist[j] > l1);

inc(j);

if j i then from[i] := j

end;

end;

begin

readln(l1,l2,l3,c1,c2,c3);

readln(n);

readln(f,t);

if f > t then

begin

i := f;

f := t;

t := i

end;

dist[1] := 0;

for i := 2 to n do readln(dist[i]);

getfrom(from1,l1);

getfrom(from2,l2);

getfrom(from3,l3);

cost[f] := 0;

for i := f + 1 to t do

begin

cost[i] := 1500000001;

if (from1[i] 0) and (cost[from1[i]] + c1 < cost[i])

then cost[i] := cost[from1[i]] + c1;

if (from2[i] 0) and (cost[from2[i]] + c2 < cost[i])

then cost[i] := cost[from2[i]] + c2;

if (from3[i] 0) and (cost[from3[i]] + c3 < cost[i])

then cost[i] := cost[from3[i]] + c3

end;

writeln(cost[t]);

end.

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

---|---|---|---|---|---|---|---|---|---|---|---|---|---|-

var l1,l2,l3,c1,c2,c3,i,j,l,r:longint;

n:integer;

a,cost:array[1..10000]of longint;

function min(x:integer):longint;

var t:integer; c,len:longint;

begin

min:=maxlongint;

for t:=x-1 downto l do

begin

len:=a[x]-a[t];

if lenl2 then c:=cost[t]+c3;

if (lenl1) then c:=cost[t]+c2;

if len

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms 秒杀...

用 if (d[j]-d[i]