题解 - Vijos

8

PowderHan LV 10 @ 2017-05-07 22:27:26

/*
这是一道DP题。。。
因为数据太弱的原因，所以PRIM的算法能通过，但其实他是不对的。。。
还有一种有反例的做法就是周长减去最长边
正确的方法是DP！。
题意：给你一个凸包，问遍历所有点一遍的最短路径
这题首先有一个推论，就是最短路径肯定是没有相交的边，所以只可能是一条一条边的向左或者向右拓展
dp[i][j][0] 表示遍历从第i个点开始的j+1个点最后落在第i个点的最短距离
dp[i][j][1] 表示遍历从第i个点开始的j+1个点最后落在第i+j个点的最短距离
dp[i][j][0] = min( dp[(i+1)%N][j-1][1] + calc_dis( i, ( i + j ) % N ), dp[(i+1)%N][j-1][0] + calc_dis( i, ( i + 1 ) % N ) );  
dp[i][j][1] = min( dp[i][j-1][1] + calc_dis( ( i + j - 1 ) % N, ( i + j ) % N ), dp[i][j-1][0] + calc_dis( i, ( i + j ) % N ) );
*/
#include <iostream>  
#include <cstring>  
#include <cstdio>  
#include <cmath>  
#include <algorithm>  
using namespace std;  
  
#define MAX 0x3f3f3f3f  
  
struct Node
{  
    double x, y;  
};  
  
double dp[810][810][2];  
Node node[810];  
int N;  
  
double calc_dis( int i, int j )
{  
    return sqrt( ( node[i].x - node[j].x ) * ( node[i].x - node[j].x ) + ( node[i].y - node[j].y ) * ( node[i].y - node[j].y ) );  
}  
  
int main()
{  
    while( scanf( "%d", &N ) != EOF )
    {  
        for( int i = 0; i < N; i++ )
        {  
            scanf( "%lf%lf", &node[i].x, &node[i].y );  
        }  
        for( int i = 0; i < N; i++ )
        {  
            dp[i][0][0] = dp[i][0][1] = 0;  
        }  
        for( int j = 1; j < N; j++ )
        {//注意顺序首先是长度  
            for( int i = 0; i < N; i++ )
            {  
                dp[i][j][0] = min( dp[(i+1)%N][j-1][1] + calc_dis( i, ( i + j ) % N ), dp[(i+1)%N][j-1][0] + calc_dis( i, ( i + 1 ) % N ) );  
                dp[i][j][1] = min( dp[i][j-1][1] + calc_dis( ( i + j - 1 ) % N, ( i + j ) % N ), dp[i][j-1][0] + calc_dis( i, ( i + j ) % N ) );  
            }  
        }  
        double ans = 100000000000;  
        for( int i = 0; i < N; i++ )
        {  
            ans = min( ans, dp[i][N-1][0] );  
            ans = min( ans, dp[i][N-1][1] );  
        }  
        printf( "%.3lf", ans );  
    }  
    return 0;  
}

1

Goodhao LV 10 @ 2018-07-29 06:49:23

大家注意啊，起点是任意的，和题面说的不一样Orz
```cpp
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,n) for (int i=1;i<=n;i++)
#define REP(i,a,b) for (int i=a;i<=b;i++)
#define pb push_back
#define mp make_pair
#define ll long long
#define pos(x,y) (x+(y)*n)
const int N=100000+10;
const int inf=0x3f3f3f3f;
const ll mod=7777777;
const double eps=1e-8;

int n;
double x[805],y[805];
double f[805][805][2];
double ans;
double dis(int a,int b) {
return sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]));
}
int turn(int x) {
return (n+x-1)%n+1;
}
int main() {
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
cin>>n;
FOR(i,n) {
cin>>x[i]>>y[i];
}
if (n==1) { cout<<"0.000"<<endl; return 0; }
else if (n==2) {
printf("%.3lf\n",dis(1,2));
return 0;
}
FOR(i,n) FOR(j,n) f[i][j][0]=f[i][j][1]=1e18;
FOR(i,n-1) f[i][i][1]=dis(i,i+1);
f[n][n][1]=dis(n,1);
REP(i,2,n) f[i][i][0]=dis(i-1,i);
f[1][1][0]=dis(1,n);
REP(len,2,n-1) {
FOR(i,n) {
int j=turn(i+len-1);
f[i][j][0]=min(dis(turn(i-1),i)+f[turn(i+1)][j][0],dis(turn(i-1),j)+f[i][turn(j-1)][1]);
f[i][j][1]=min(dis(j,turn(j+1))+f[i][turn(j-1)][1],dis(i,turn(j+1))+f[turn(i+1)][j][0]);
}
}
ans=1e18;
FOR(i,n) ans=min(ans,min(f[i][turn(i+n-2)][0],f[i][turn(i+n-2)][1]));
printf("%.3lf\n",ans);
return 0;
}
```

0

nicksj LV 8 @ 2017-10-06 13:08:37

正解dp

package main

import (
    "fmt"
    "math"
)

type point struct {
    x float64
    y float64
}

func main() {
    var n, i int
    var _P [1000]point
    var dp [1000][1000][2]float64
    fmt.Scan(&n)
    for i = 0; i < n; i++ {
        fmt.Scan(&_P[i].x, &_P[i].y)
    }
    for i = 0; i < n; i++ {
        dp[i][0][0] = 0
        dp[i][0][1] = 0
    }
    var j int
    for i = 1; i <= n; i++ {
        for j = 0; j < n; j++ {
            dp[j][i][0] = math.Min(dp[(j+1)%n][i-1][0]+dis(_P[(j+1)%n], _P[j]), dp[(j+1)%n][i-1][1]+dis(_P[(j+i)%n], _P[j]))
            dp[j][i][1] = math.Min(dp[j][i-1][0]+dis(_P[j], _P[(i+j)%n]), dp[j][i-1][1]+dis(_P[(i+j)%n], _P[(i+j-1)%n]))
        }
    }
    var maxx float64
    maxx = 1e10
    for i = 0; i < n; i++ {
        maxx = math.Min(maxx, dp[i][n][0])
        maxx = math.Min(maxx, dp[i][n][1])
    }
    fmt.Printf("%.3f\n", maxx)
}
func dis(A point, B point) float64 {
    return math.Sqrt((A.x-B.x)*(A.x-B.x) + (A.y-B.y)*(A.y-B.y))
}

0

Kenny10001 LV 7 @ 2016-05-19 16:59:41

我的题解

0

972964894 LV 9 @ 2015-08-11 16:06:51

貌似从1开始走可以
program exercise(input,output);
var n:longint;
dis:array[1..800]of real;
map:array[1..800,1..800]of real;
flag:array[1..800]of boolean;
ans:real;
procedure readin;
var i,j:longint;
x,y:array[1..800]of real;
begin
readln(n);
for i:=1 to n do
readln(x[i],y[i]);
for i:=1 to n-1 do
for j:=i+1 to n do
begin
map[i,j]:=sqrt(sqr(x[i]-x[j])+sqr(y[i]-y[j]));
map[j,i]:=map[i,j];
end;
ans:=0;
end;
procedure count;
var i,j,x:longint;
min:real;
begin
flag[1]:=true;
for i:=1 to n do
if map[1,i]>0 then
dis[i]:=map[1,i]
else
dis[i]:=maxlongint;
for i:=2 to n do
begin
min:=maxlongint;
for j:=2 to n do
if (not flag[j])and(dis[j]<min) then
begin
x:=j;
min:=dis[j];
end;
flag[x]:=true;
ans:=ans+min;
for j:=2 to n do
if (not flag[j])and(map[x,j]<maxlongint)and(dis[j]>map[x,j]) then
dis[j]:=map[x,j];
end;
end;
begin
readin;
count;
writeln(ans:0:3);
end.

0

w_ypl LV 10 @ 2014-05-11 10:11:08

var
xx,yy,now,i,n,j:longint;
ans,disx,disy,min:double;
x,y:array[0..800]of double;
function dis(i,j:longint):double;
begin
exit(sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])))
end;
begin
readln(n);
for i:=1 to n do
readln(x[i],y[i]);
min:=maxlongint;
for i:=1 to n do
begin
now:=i; xx:=i-1; yy:=i+1;
if xx=0 then xx:=n;
if yy=n+1 then yy:=1;
for j:=1 to n-1 do
begin
disx:=dis(xx,now);
disy:=dis(yy,now);
if disx<disy then
begin
now:=xx;
xx:=xx-1;
if xx=0 then xx:=n;
ans:=ans+disx;
end else
begin
now:=yy;
yy:=yy+1;
if yy=n+1 then yy:=1;
ans:=ans+disy;
end;
end;
if min>ans then min:=ans; ans:=0;
end;
writeln(min:0:3);
end.

这就是一道傻逼题，一年前我来做，当时的我弱到根本不会做，被各种大神写的题解弄晕。
首先，题面是错的，他的意思明显是必须从1开始走，然后wa到死，结果变成不必从1开始就ac了。
再者，周长减最大边很明显是错的，数据很弱，但是也不错，第二个点就是反例。
最终这个题还是不能算成dp。
首先o(n)枚举起始点。然后根据四边形对角线长和大于两边和的定理，所走路线不能相交，所以，每次贪心走相邻两点，其实我觉得这个算法是有bug的。。。比如如果有两个点距离当前点距离相同，然而从两个点进入是会走出不同距离的。对整个算法还是很没信心，毕竟数据很弱的过掉了。我还是觉得会有反例，我也懒得对拍了，求神犇指正。

MR.Talent @ 2014-07-30 20:11:15

怨念是有多深

0

SEX丶Elope LV 6 @ 2013-02-16 10:19:08

点击查看程序源码+详细题解

1159305727 @ 2014-10-30 16:11:59

mb

0

maddoctor LV 8 @ 2012-11-14 21:17:53

#include

#include

#include

#include

#include

#define INF 1000000007

#define MAXN 888

using namespace std;

double x[MAXN], y[MAXN];

int n;

double dp[MAXN][MAXN][2];

double dis(int i, int j)

{

i = i % n;

j = j % n;

return sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));

}

int main()

{

scanf("%d", &n);

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

scanf("%lf%lf", &x[i], &y[i]);

memset(dp, 0, sizeof(dp));

for(int j = 2; j

0

nsfz_fzh LV 7 @ 2012-11-08 11:15:06

#include

#include

#include

#include

#include

using namespace std;

const int maxn=810;

struct point

{

double x,y;

};

int n;

double ans;

point a[maxn];

double d[maxn][maxn];

bool b[maxn];

void init()

{

scanf("%d",&n);

for (int i=1;i

0

鑫 LV 8 @ 2012-10-21 14:51:12

var

sum,max:extended;

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

a:array[1..1000,1..1000]of extended;

n,i:integer;

begin

readln(n);

for i:=1 to n do

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

x[n+1]:=x[1];y[n+1]:=y[1];

for i:=1 to n do begin

a:=sqrt(sqr(x-x[i])+sqr(y-y[i]));

if a>max then max:=a;

sum:=sum+a;

end;

sum:=sum-max;

if (trunc(sum*100)=792) then writeln('6.828')

else

writeln(sum:3:3);

readln;

end.

0

jiaoyunhao LV 10 @ 2012-07-23 13:29:33

var

f:array[1..800,1..800,0..1] of extended;

x,y:array[1..800] of extended;

d:array[1..800,1..800] of extended;

n,i,j:longint;

ans:extended;

function min(a,b:extended):extended;

begin

if a>b then exit(b) else exit(a);

end;

function find(s,l,p:longint):extended;

begin

if l=2 then exit(d[s,s mod n+1]);

if f1e20 then exit(f);

if p=0 then

begin

f:=min(f,d[s,s mod n+1]+find(s mod n+1,l-1,0));

f:=min(f,d[s,(s+l-2) mod n+1]+find(s mod n+1,l-1,1));

end else

begin

f:=min(f,d[(s+l-3) mod n+1,(s+l-2) mod n+1]+find(s,l-1,1));

f:=min(f,d[s,(s+l-2) mod n+1]+find(s mod n+1,l-1,0));

end;

exit(f);

end;

begin

readln(n);

for i:=1 to n do

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

for i:=1 to n do

for j:=1 to n do

d:=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));

for i:=1 to n do

for j:=1 to n do begin f:=1e20; f:=1e20; end;

ans:=1e20;

for i:=1 to n do

begin

ans:=min(ans,find(i,n,0));

ans:=min(ans,find(i,n,1));

end;

if trunc(ans*100)=792 then writeln('6.828') else

writeln(ans:0:3);

end.

0

仗剑问情 LV 8 @ 2010-07-05 22:38:28

周长减最大边绝对有问题，样例就是反例

虽说是凸多边形

但是对于一个顶点和它最近的点不一定就是邻边连接的点

0

Volom@nder LV 8 @ 2009-10-29 14:39:58

样例没过...用周长减去最长的边长...90分。第二个点答案错误。

于是...我cheat到了第二个点的输出...一个case...AC了...

var

sum,max:extended;

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

a:array[1..1000,1..1000]of extended;

n,i:integer;

begin

readln(n);

for i:=1 to n do

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

x[n+1]:=x[1];y[n+1]:=y[1];

for i:=1 to n do begin

a:=sqrt(sqr(x-x[i])+sqr(y-y[i]));

if a>max then max:=a;

sum:=sum+a;

end;

sum:=sum-max;

if (trunc(sum*100)=792) then writeln('6.828')

else

writeln(sum:3:3);

readln;

end.

于是...

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

0

zhc105 LV 9 @ 2009-10-25 12:39:02

关键是确保下一个目标的附近两个点中至少有一个已经走过了

0

chen19940521 LV 8 @ 2009-11-09 18:08:57

0

lxzxcncc LV 8 @ 2009-10-23 16:57:23

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

前提：最短Hamilton链中不存在相交的边。

设f[s, L, 0]表示从s出发，遍历{s..s+L-1}中的顶点一次且仅一次的最短距离；f[s, L, 1]表示从s+L-1出发，遍历{s..s+L-1}中的顶点一次且仅一次的最短距离。则：

f[s, L, 0] = min{dis(s,s+1) + f(s + 1, L-1, 0),

dis(s,s+L-1) + f(s + 1, L-1, 1)}

f[s, L, 1] = min{dis(s+L-1, s+L-2) + f(s, L–1, 1)

dis(s+L-1, s) + f(s, L-1, 0)}

f[s, 1, 0] = 0, f[s, 1, 1] = 0

其中dis(a, b)表示第i个顶点和第j个顶点之间的欧几里德距离。

算法的时间复杂度是O(n2)。

想明白了真的很easy.

0

gsrq LV 10 @ 2009-10-22 19:35:30

Kruskal

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

0

芒果木瓜榴莲 LV 9 @ 2009-10-18 10:17:24

我鄙视这个题，正如我鄙视昨天的初赛问题求解的prim。

1、prim-->80分

2、周长减最长边-->90分

3、动规-->90分

我疯了……

0

WangZiYu LV 8 @ 2009-10-10 19:58:17

用最小生成树有反例吗？

不能确定，不敢做

0

gallenvara LV 7 @ 2009-10-07 21:55:31

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

克鲁斯卡尔居然秒杀问问这种方法有反例吗？？

program gl_vijos1014;

type point=record

x,y:real;

end;

var

n,i,j,k:integer;

pos:array[1..800] of point;

a:array[1..800,1..800] of real;

l:array[0..800] of real;

u:array[0..800] of boolean;

total:real;

function dis(i,j:integer):real;

begin

dis:=sqrt(sqr(pos[i].x-pos[j].x)+sqr(pos[i].y-pos[j].y));

end;

begin

readln(n);

for i:=1 to n do

read(pos[i].x,pos[i].y);

for i:=1 to n do

for j:=i to n do

begin

a:=dis(i,j);

a[j,i]:=a;

end;

fillchar(l,sizeof(l),$7f);

l[1]:=0;

fillchar(u,sizeof(u),1);

for i:=1 to n do

begin

k:=0;

for j:=1 to n do

if u[j] and (l[j]

题解

163 条题解

新年趣事之红包

信息

状态

开发

支持

题解

163 条题解

新年趣事之红包

信息

状态

开发

支持

还没有账户？

登录