# 69 条题解

• @ 2017-07-27 17:25:16
``````#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <deque>
#include <limits>
#include <string>
#include <sstream>
using namespace std;

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

struct segment_tree_1
{
int l,r,mid;
double x;
};

int n;
double len,m;
double f[1000+1];
double v[1000+1];
double w[1000+1];
segment_tree_1 st_v[2*1024+2];
segment_tree_1 st_w[2*1024+2];

void build_segment_tree_v(int p,int l,int r)
{
st_v[p].l=l,st_v[p].r=r,st_v[p].mid=(l+r)/2;
if (l<r)
{
if (l<=st_v[p].mid)
build_segment_tree_v(p*2,l,st_v[p].mid);
if (st_v[p].mid+1<=r)
build_segment_tree_v(p*2+1,st_v[p].mid+1,r);
}
if (l==r)
st_v[p].x=v[l];
else
st_v[p].x=min(st_v[p*2].x,st_v[p*2+1].x);
}

void build_segment_tree_w(int p,int l,int r)
{
st_w[p].l=l,st_w[p].r=r,st_w[p].mid=(l+r)/2;
if (l<r)
{
if (l<=st_w[p].mid)
build_segment_tree_w(p*2,l,st_w[p].mid);
if (st_w[p].mid+1<=r)
build_segment_tree_w(p*2+1,st_w[p].mid+1,r);
}
if (l==r)
st_w[p].x=w[l];
else
st_w[p].x=st_w[p*2].x+st_w[p*2+1].x;
}

double sum_v(int p,int l,int r)
{
if (st_v[p].l==l&&st_v[p].r==r)
return st_v[p].x;
else if (r<=st_v[p].mid)
return sum_v(p*2,l,r);
else if (l>=st_v[p].mid+1)
return sum_v(p*2+1,l,r);
else
return min(sum_v(p*2,l,st_v[p].mid),sum_v(p*2+1,st_v[p].mid+1,r));
}

double sum_w(int p,int l,int r)
{
if (st_w[p].l==l&&st_w[p].r==r)
return st_w[p].x;
else if (r<=st_w[p].mid)
return sum_w(p*2,l,r);
else if (l>=st_w[p].mid+1)
return sum_w(p*2+1,l,r);
else
return sum_w(p*2,l,st_w[p].mid)+sum_w(p*2+1,st_w[p].mid+1,r);
}

double sum_t(int p,int l,int r)
{
return len/sum_v(p,l,r);
}

int main()
{
while (~scanf("%lf%lf%d",&m,&len,&n))
{
for (int i=1;i<=n;i++)
scanf("%lf%lf",&w[i],&v[i]);
build_segment_tree_v(1,1,n);
build_segment_tree_w(1,1,n);
f[0]=0;
for (int i=1;i<=n;i++)
{
f[i]=oo_max;
for (int j=i;j>=1;j--)
{
double tot_t=sum_t(1,j,i),tot_w=sum_w(1,j,i);
if (tot_w<=m)
f[i]=min(f[i],f[j-1]+tot_t);
}
}
printf("%.1lf\n",f[n]*60);
}
}
``````
• @ 2017-07-27 17:26:30

这么H2O的题，DP+Segment Tree来H2O过

• @ 2009-09-13 17:34:52

额.....原来......第八个点是w[i]的累加值崩了........

估计v[i]和len max也得崩.......

• @ 2009-09-02 13:56:01

天杀的第八个点

• @ 2016-08-27 17:00:36
``````#include <iostream>
#include <iomanip>
using namespace std;
int n;
double _max,len,tot,v[1005],f[1005],w[1005];
double time(int a,int b){
double y=99999999;
for (int i=a;i<=b;i++)
if (v[i]<y) y=v[i];
return (len/y);
}
int main(){
ios::sync_with_stdio(false);
cin >> _max >> len >> n;
for (int i=1;i<=n;i++) cin >> w[i] >> v[i];
f[0]=0;
f[1]=len/v[1];
for (int i=2;i<=n;i++){
f[i]=99999999;
for (int j=i;j>=1;j--){
tot=0;
for (int k=j;k<=i;k++) tot+=w[k];
if (tot>_max) break;
if (f[j-1]+time(j,i)<f[i]) f[i]=f[j-1]+time(j,i);
}
}
cout<<setiosflags(ios::fixed) << setprecision(1) << f[n]*60 << "\n";
}
``````
• @ 2016-06-26 13:33:45

var w,v:array[0..1200] of longword;
t:array[0..1200]of double;
max,len,n,i,j,weight:longword; time,velocity:double;

function min(x,y:double):double;
begin
if x<y then exit(x) else exit(y);
end;

begin
for i:=1 to n do readln(w[i],v[i]);
t[1]:=len/v[1];
for i:=2 to n do begin
weight:=w[i]; velocity:=v[i]; time:=T[I-1]+LEN/V[I];
for j:=i-1 downto 1 do begin
weight:=weight+w[j];
if weight>max then break
else begin
velocity:=min(velocity,v[j]);
time:=min(time,len/velocity+t[j-1]);
end;
end;t[i]:=time; end;
writeln(t[n]*60:0:1);
end.

• @ 2010-03-10 20:53:48

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

#include

using namespace std;

const int N=1011;

const double MAXN=1000000.0;

unsigned long long w[N][N],MAX,len,n;

double v[N][N],f[N];

void init(void)

{

int x;

cin>>MAX>>len>>n;

for (int i=1;i>w[i][i]>>x;

v[i][i]=double(len)/double(x);

}

for (int i=1;iv[j+1][i]+f[j])

f[i]=v[j+1][i]+f[j];

}

}

printf("%.1lf",f[n]*60.0);

}

int main(void)

{

init();

dp();

return 0;

}

• @ 2009-11-09 16:53:47

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

秒杀，得注意读题啊

f[i]表示前i个汽车通过的最小时间

f[i]=min{f[j-1]+time{j,i}}

time[j,i]我是拿线段树写的

总的时间复杂度O(N^2*logN)

f[i]=min{f[j-1]+time[j,i]}

• @ 2009-11-07 13:37:16

把这道题跟P1488混到一起了，方程应该是一维的，时空效率皆为O(N^2)

• @ 2009-11-06 11:17:01

要什么预处理啊，直接DP不就行了

program p1355;

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

car:array[0..1000,1..2]of int64;

sum,t,n,i,j,k,max,len,v,w:longint;

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

begin

if a

• @ 2009-11-02 16:59:22

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

O(n^2)预处理

O(N^2)DP

• @ 2009-10-28 20:24:15

f[i]表示前i辆车的所消耗的最小时间

w[x,y]表示[x,y]区间内wi的总和

t[x,y]表示[x,y]区间的车辆通过所需的时间

则有

f[i]=min(f[k]+t[k+1,i])

其中要满足：

1.k

• @ 2009-10-24 15:20:19

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

var maxw,len,n,i,j:longint;

w,v:array[0..1003]of longint;

f:array[0..1003]of real;

a,b:array[0..1003,0..1003]of int64;

function min(x,y:real):real;

begin

if x>y then min:=y else min:=x;

end;

begin

fillchar(f,sizeof(f),0);

fillchar(a,sizeof(a),0);

fillchar(b,sizeof(b),0);

for i:=0 to n do

for j:=0 to n do b:=99999999;

for i:=1 to n do readln(w[i],v[i]);

for i:=1 to n do

for j:=i to n do

begin

a:=a+w[j];

if b>v[j] then b:=v[j]

else b:=b;

end;

for i:=1 to n do

begin

f[i]:=99999999;

for j:=1 to i do

begin

if (a[j,i]

• @ 2009-10-19 12:48:50
• @ 2009-10-18 12:43:16

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

一次AC水题

• @ 2009-09-20 21:18:02

好久没一次AC了。。。

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• @ 2009-09-02 07:05:38

这题做的，整得我的心哪，老霸道了……

#include

#include

using namespace std;

double w[1001], s[1001], f[1001];

int main(){

long i, j, k, n;

double m, ww, wl, l;

cin>>wl>>l>>n;

for (i = 1; i >w[i]>>s[i];

f[0] = 0; w[0] = 0;

for (i = 1; i = 1; j--){

ww += w[j];

if (ww

• @ 2009-08-22 11:46:40

做了一个上午，总算AC了，参考了一下网上的，有的还是不太理解，就算是默写吧……

#include

using namespace std;

double f[1001]={},TIME,speed,weight,smax,len;

long w[1001]={},v[1001]={},t,n;

bool flag;

int main(){

cin>>smax>>len>>n;

for(int i=1;i>w[i]>>v[i];

}

f[1]=len/v[1];

for(int i=2;i

• @ 2009-08-11 16:43:28

第八个点要unsigned long

• @ 2009-08-07 21:14:43

囧第八个点

30行小程序

• @ 2009-08-07 20:30:19

第八个点要int64

ID
1355

4

(无)

1094

445

41%

4