我无语了

。。。居然一次就过了。。建了一个囧图然后SPFA。。

囧死掉，细节啊，交了6次才过……

其中有2次是因为忘保留两位小数，有3次是因为忘关文件操作……

本题AC率被我活生生刷下1%……

跨立试验 + SPFA

Dijkstra+判断直线相交，一次AC。。。

DP

设f(i)为标号i的节点到初始节点的长度

f(i)=min(f(j)+dis(i,j)(i,j可达))

程序大概40～50行左右，我写的比较冗长47行

program P1013;

var

x:array[-1..20]of real;

a,f:array[-1..80]of real;

n,i,j:longint;

ans,dis:real;

s:boolean;

function min(b,c:real):real;

begin

if b=0

then lb:=b shr 2

else lb:=-1;

lc:=c shr 2;pd:=true;

k:=(a-a[c])/(x[lb]-x[lc]);

for l:=lb+1 to lc-1 do

begin

d:=a+k*(x[l]-x[lb]);

if (da[4*l+3])

then begin

pd:=false;

break;

end;

end;

dis:=sqrt(sqr(a-a[c])+sqr(x[lb]-x[lc]));

end;

begin

readln(n);

x[-1]:=0;a[-1]:=5;x[n]:=10;a[4*n]:=5;

for i:=0 to n-1 do

readln(x[i],a,a,a,a);

for i:=0 to 4*n do

f[i]:=1e10;

for i:=0 to 4*n do

for j:=-1 to 4*(i shr 2)-1 do

if pd(j,i)

then f[i]:=min(f[i],dis+f[j]);

end.

程序千万不要直接考哦！少了一个语句

WS的打了90+行....结果1次ms..

第一个一遍AC的 o(∩_∩)o...

简单模拟 加一个判断函数即可

相似三角+DP为什么第四个点比正确答案少0.05...

细节问题

http://hi.baidu.com/%CB%D5%CC%DAsauterne

shit 一个变量打错了

简单的DP，如果能够从(x1,y1)不穿墙直接到达(x2,y2)（x2>x1），那么

dis[x1,y1]=min{dis[x1,y1],dis[x2,y2]+len}，其中len是(x1,y1)到(x2,y2)的距离

可惜我看错了题目，以为n

叉积即可

终于AC！！！

就是有点麻烦而已。

一次搞定：D 89行……

起点编到一半才想起来 于是加了个数列第-1项 但 -1div4=1div4=0所以起点和其他点的联通情况最好单独判断。

附判断函数：

var

cost:array[-1..80,-1..80]of real;

x,y:array[-1..80]of real;

function bool(a,b:integer):boolean;

var

i,j:integer;

begin

for i:=(a div 4)+1 to (b div 4)-1 do

begin

if (y-y[a])/(x-x[a])>(y-y[a])/(x-x[a]) then exit(false);

if ( (y-y[a])/(x-x[a])(y-y[a])/(x-x[a]) ) then exit(false);

if (y-y[a])/(x-x[a])(y-y[a])/(x-x[a]) then exit(false);

if ( (y-y[a])/(x-x[a])(y-y[a])/(x-x[a]) ) then exit(false);

if (y-y[a])/(x-x[a])

type

dot=record

x,y:double;

end;

line=record

a,b:dot;

end;

var

n,p,cl,op:longint;

d:array[0..100]of dot;

l:array[0..70]of line;

fir:array[0..100]of longint;

dist:array[0..100]of double;

used:array[0..100]of boolean;

w:array[0..100*100]of double;

u,last,q:array[0..100*100]of longint;

function cj(a,b,c:dot):double;

begin

cj:=(b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);

end;

function can(a,b:dot):boolean;

var

i:longint;

begin

for i:=1 to ((n-2)div 4)*3 do

if (cj(a,b,l[i].a)*cj(a,b,l[i].b)

额。。不是很难，但是要细心一点。

我自己中的招：没有判断能否从起点直接到达。

我记得代码不长啊,怎么到这里显得这么长？？

#include

#include

using namespace std;

double f[30][5],a[30],b[30][5];

int n;

bool check(int x1,int y1,int x2,int y2)

{

for (int i=x1+1;ib[i][2]&&yy=0) return f[x][y];

double s=10000000.23;

if (check(x,y,n+1,0)) return hypot(a[n+1]-a[x],abs(b[n+1][0]-b[x][y]));

for (int i=x+1;ib[i][1]>>b[i][2]>>b[i][3]>>b[i][4];

printf("%.2f\n",search(0,0));

return 0;

}

直接搜索……当然加了记忆化。本身就是dp，最开始时按搜索想的，就这么写了……

发现我的代码写的又丑又长。。。

#include

#include

using namespace std;

const int MaxN = 100;

struct Point

{

double x, y;

} P[MaxN];

struct Line

{

double x, a, b;

} L[MaxN];

double G[MaxN][MaxN];

int N;

bool Used[MaxN];

double Ans[MaxN];

double Dis(int a, int b)

{

return sqrt((P[a].x - P.x)*(P[a].x - P.x)+(P[a].y - P.y)*(P[a].y - P.y));

}

double max(double a, double b)

{

if (a > b) return a;

else return b;

}

double min(double a, double b)

{

if (a > b) return b;

else return a;

}

double Multi(Point pt1, Point pt2, Point pt0)

{//向量的X乘，不是点乘

//pt0视为原点

//返回结果大于0pt1在PT2的在顺时针方向

// < 0在逆时针方向

// == 0两向量共线

double x1 = pt1.x - pt0.x;

double y1 = pt1.y - pt0.y;

double x2 = pt2.x - pt0.x;

double y2 = pt2.y - pt0.y;

return x1 * y2 - x2*y1;

}

bool Chk(Line T, int a, int b)

{

Point p1, p2, q1, q2;

p1.x = T.x, p1.y = T.a;

p2.x = T.x, p2.y = T.b;

q1 = P[a];

q2 = P;

if (!(max(p1.x, p2.x) >= min(q1.x, q2.x) && max(q1.x, q2.x) >= min(p1.x, p2.x) &&

max(p1.y, p2.y) >= min(q1.y, q2.y) && max(q1.y, q2.y) >= min(p1.y, p2.y)))

return 0;

double t1 = Multi(q1, p2, p1);

double t2 = Multi(q2, p2, p1);

double t = t1*t2;

if (t > 0) return 0;

t1 = Multi(p1, q2, q1);

t2 = Multi(p2, q2, q1);

t = t1*t2;

if (t > 0) return 0;

return 1;

}

bool Chk(int a, int b)

{

if (a != 0)

{

if ((a - 1) / 4 + 1 == (b - 1) / 4) return 1;

if ((a - 1) / 4 == (b - 1) / 4) return 0;

bool Flag = 0;

for (int i = (a - 1) / 4 + 1; i < (b - 1) / 4; i++)

if (!Chk(L[i * 2 + 1], a, b) && !Chk(L[i * 2 + 2], a, b))//判断a、b的是否和一段空的线段存在交点

{

Flag = 1;

break;

}

if (!Flag) return 1;

}

else

{

if ((b - 1) / 4 == 0) return 1;

bool Flag = 0;

for (int i = 0; i < (b - 1) / 4; i++)

if (!Chk(L[i * 2 + 1], a, b) && !Chk(L[i * 2 + 2], a, b))//判断a、b的是否和一段空的线段存在交点

{

Flag = 1;

break;

}

if (!Flag) return 1;

}

return 0;

}

int main()

{

scanf("%d", &N);

for (int i = 0; i < N; i++)

{

double x, a1, a2, b1, b2;

scanf("%lf%lf%lf%lf%lf", &x, &a1, &b1, &a2, &b2);

P[i * 4 + 1].x = x, P[i * 4 + 1].y = a1;

P[i * 4 + 2].x = x, P[i * 4 + 2].y = b1;

P[i * 4 + 3].x = x, P[i * 4 + 3].y = a2;

P[i * 4 + 4].x = x, P[i * 4 + 4].y = b2;

L[i * 2 + 1].x = x, L[i * 2 + 1].a = a1, L[i * 2 + 1].b = b1;

L[i * 2 + 2].x = x, L[i * 2 + 2].a = a2, L[i * 2 + 2].b = b2;

}

P[0].x = 0, P[0].y = 5;

P[N * 4 + 1].x = 10, P[N * 4 + 1].y = 5;

for (int i = 0; i

自己DP写得太烂了，所以还是用最短路吧……