编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

貌似坐标是小数

封人号SB

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

方程不难，但是数组开小了 Orz………………

没秒杀是个遗憾。

日，点的坐标居然可以不是整数

害得我WA一次

点的坐标不是整数

var

a,b:array[0..1000]of real;

f:array[0..1000,0..1000]of real;

n:longint;

function dist(k1,k2:longint):real;

begin

dist:=sqrt(sqr(a[k1]-a[k2])+sqr(b[k1]-b[k2]));

end;

procedure dp;

var

i,j,k:longint;

temp:real;

begin

for i:=1 to n-1 do

for j:=i+1 to n do

if a[i]>a[j] then

begin

temp:=a[i];a[i]:=a[j];a[j]:=temp;

temp:=b[i];b[i]:=b[j];b[j]:=temp;

end;

for i:=1 to n do

for j:=1 to n do f[i][j]:=1e24;

f[2][1]:=dist(1,2);

for i:=1 to n do

for j:=1 to n do

begin

if i>j+1 then f[i][j]:=f[j]+dist(i-1,i);

if i=j+1 then for k:=1 to i-2 do

if f[i][j]>f[k]+dist(k,i) then f[i][j]:=f[k]+dist(k,i);

end;

f[n][n]:=1e24;

for i:=1 to n-1 do

if f[n][n]>f[n][i]+dist(i,n) then f[n][n]:=f[n][i]+dist(i,n);

writeln(f[n][n]:0:2);

end;

procedure init;

var

i:longint;

begin

readln(n);

for i:=1 to n do readln(a[i],b[i]);

end;

begin

init;

dp;

end.

题目输入有问题。。。是实数 而不是整型。。。。

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

数据有点弱，还以为要用double

方程和各位差不多

这道题的动归方程很巧妙：

方程：f=min{f+d,f+d};{i

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

f[j,i]:=min( f[j,i-1]+d(i,i-1) , f+d(j,i-1) );

想了好久终于想明白了....

结果因为快排一个变量打错，交N次....

双进程DP的模型大多这样：

F 表示 第1个人走到i，第2个人走到J的最短路程

此题数据够弱，

1.同一直线上的情况没考虑都AC

2.有可能没有回路，但是数据没有这种情况

var i,j,n:integer;

s,t:real;

f:array[0..1000,0..1000] of real;

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

procedure quick(s,t:integer);

var i,j:integer;

z1,z2:real;

begin

z1:=x[(s+t) div 2];

z2:=y[(s+t) div 2];

x[(s+t) div 2]:=x;

y[(s+t) div 2]:=y;

x:=z1;

y:=z2;

i:=s;

j:=t;

while i

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

秒杀

动规方程：

F表示I点开始返回到I-1点的最小路径

则 F=MAX(F[J+1]+D+DIS)

var

i,j,k,l,m,n,z:Longint;

f:array[0..1000,0..1000] of real;

a:array[0..1000] of record

x,y:Longint;

end;

qq:array[0..1000] of real;

dis:array[0..1000,0..1000] of real;

procedure pai(l,r:longint);

var

i,j,k,m:Longint;

begin

i:=l;

j:=r;

k:=a[i].x;

m:=a[i].y;

while i

#include

#include

#include

#include

#include

using namespace std;

const int MaxN = 1000 + 10;

struct node

{

int x, y;

}a[MaxN];

int n;

double dp[MaxN][MaxN];

bool cmp(const node& a, const node& b)

{

return a.x < b.x;

}

#define sqr(a) ((a) * (a))

#define dist(a, b) (sqrt(double(sqr(double(a.x - b.x)) + sqr(double(a.y - b.y)))))

int main()

{

cin >> n;

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

cin >> a[i].x >> a[i].y;

sort(a, a + n, cmp);

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

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

dp[i][j] = 1e60;

dp[0][0] = 0;

int i,j;

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

for (j = 0; j < n; ++j)

{

int t = min(n - 1, max(i, j) + 1);

dp[i][t] = min(dp[i][t], dp[i][j] + dist(a[j], a[t]));

dp[t][j] = min(dp[t][j], dp[i][j] + dist(a[i], a[t]));

}

printf("%.2lf\n", dp[n - 1][n - 1]);

return 0;

}

比较暴力，还算短

要求是双调路径。。

这个题首先要拆成两个人，看成是分别走，路径没有重复的最短路。

这个题如果设f表示第一个人到i，第二个人到j的最短路，很容易设计出一个O（n^3）的方法，可惜会超时。

这个题有一个特点，就是所有点之间都可以互相到达，而且距离跟拓扑序列几乎成正比。于是就诞生了一个O（n^2）的算法。每次计算f时，显然只需要计算i>=j的情况就可以了。此时，考虑最后的一步。

有两种情况

1． 从j-1走到i，此时就和状态f[j,j-1]有关。

2． 从j-1走到j，此时就和状态f有关。

也许有的人会认为可能是从i-1走到i，这种情况不能考虑！！对于前面的点，如果你考虑了i-1到i的情况，你无法保证j走不到i-1，也就是保证不了没有后效性，因为j的走法不是当前状态能决定的！！但是如果j-1到j的话，f已经是一个固定的状态，，不会再有点走到j-1！！所以没有问题！！于是，每次走的时候，为了保证没有后效性，前面的一个人必须从后面的人在后面的点飞过去，相当于枚举了初始点。这样就只剩下了两种转移，一种是后面的人一步一步走，另一种是前面的人飞过去。

能否来个C的DP，说的不是很懂 来份代码

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

坐标也要用实行，长整型要挂掉！！！

坐标也要用实行，长整型要挂掉！！！

坐标也要用实行，长整型要挂掉！！！

坐标也要用实行，长整型要挂掉！！！

坐标也要用实行，长整型要挂掉！！！

var i,j,n:integer;

s,t:real;

f:array[0..1000,0..1000] of real;

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

procedure quick(s,t:integer);

var i,j:integer;

z1,z2:real;

begin

z1:=x[(s+t) div 2];

z2:=y[(s+t) div 2];

x[(s+t) div 2]:=x;

y[(s+t) div 2]:=y;

x:=z1;

y:=z2;

i:=s;

j:=t;

while i

ＮＥＷ　ＷＡＹ－－－

可转化为最小费用最大流模型解决！

时空复杂度不错，只是编程复杂度嘛～～

还是用ＤＰ啦．

( 2007-11-12 15:06:13 ah_gj)

...

我又看到班班的留言了...哎..为什么不留下来呢...

我们这么迟都没有解决这题...最近才知道最小费用流..#

...真是惭愧..

#24...这题可以用最小费用流作么?..

是不是应该比较一下这题..?

http://www.nocow.cn/index.php/Translate:USACO/tour