122 条题解
-
0hxlong LV 10 @ 2009-09-05 23:14:43
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 0ms
├ 测试数据 05:答案正确... 0ms
├ 测试数据 06:答案正确... 0ms
├ 测试数据 07:答案正确... 0ms
├ 测试数据 08:答案正确... 0ms
├ 测试数据 09:答案正确... 0ms
├ 测试数据 10:答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分:100 有效耗时:0ms
貌似坐标是小数 -
02009-09-05 14:33:18@
封人号SB
-
02009-09-01 20:09:01@
Accepted 有效得分:100 有效耗时:132ms
方程不难,但是数组开小了 Orz………………
没秒杀是个遗憾。 -
02009-08-30 11:12:19@
日,点的坐标居然可以不是整数
害得我WA一次 -
02009-08-25 10:45:16@
点的坐标不是整数
-
02009-08-15 11:41:53@
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.
题目输入有问题。。。是实数 而不是整型。。。。 -
02009-08-11 20:46:00@
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 0ms
├ 测试数据 05:答案正确... 0ms
├ 测试数据 06:答案正确... 0ms
├ 测试数据 07:答案正确... 0ms
├ 测试数据 08:答案正确... 0ms
├ 测试数据 09:答案正确... 0ms
├ 测试数据 10:答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分:100 有效耗时:0ms
数据有点弱,还以为要用double
方程和各位差不多 -
02009-08-11 18:08:53@
这道题的动归方程很巧妙:
方程:f=min{f+d,f+d};{i -
02009-08-05 10:35:00@
编译通过...
├ 测试数据 01:答案正确... 0ms
├ 测试数据 02:答案正确... 0ms
├ 测试数据 03:答案正确... 0ms
├ 测试数据 04:答案正确... 0ms
├ 测试数据 05:答案正确... 0ms
├ 测试数据 06:答案正确... 0ms
├ 测试数据 07:答案正确... 0ms
├ 测试数据 08:答案正确... 0ms
├ 测试数据 09:答案正确... 0ms
├ 测试数据 10:答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分:100 有效耗时:0msf[j,i]:=min( f[j,i-1]+d(i,i-1) , f+d(j,i-1) );
-
02009-08-02 11:10:38@
想了好久终于想明白了....
结果因为快排一个变量打错,交N次.... -
02009-07-21 13:16:02@
双进程DP的模型大多这样:
F 表示 第1个人走到i,第2个人走到J的最短路程此题数据够弱,
1.同一直线上的情况没考虑都AC
2.有可能没有回路,但是数据没有这种情况 -
02009-07-09 14:58:58@
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 -
02009-07-09 13:24:01@
编译通过...
├ 测试数据 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) -
02009-11-09 21:30:46@
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 -
02009-07-06 22:51:08@
#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;
}
比较暴力,还算短 -
02009-07-02 15:43:47@
要求是双调路径。。
-
02009-06-15 22:42:33@
这个题首先要拆成两个人,看成是分别走,路径没有重复的最短路。
这个题如果设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!!所以没有问题!!于是,每次走的时候,为了保证没有后效性,前面的一个人必须从后面的人在后面的点飞过去,相当于枚举了初始点。这样就只剩下了两种转移,一种是后面的人一步一步走,另一种是前面的人飞过去。
-
02009-04-27 18:16:09@
能否来个C的DP,说的不是很懂 来份代码
-
02009-04-26 22:22:00@
编译通过...
├ 测试数据 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 -
02009-03-25 19:39:52@
NEW WAY---
可转化为最小费用最大流模型解决!
时空复杂度不错,只是编程复杂度嘛~~
还是用DP啦.
( 2007-11-12 15:06:13 ah_gj)
...
我又看到班班的留言了...哎..为什么不留下来呢...
我们这么迟都没有解决这题...最近才知道最小费用流..#
...真是惭愧..#24...这题可以用最小费用流作么?..
是不是应该比较一下这题..?
http://www.nocow.cn/index.php/Translate:USACO/tour