题解 - Vijos

1

Sky1231 (sky1231) LV 10 @ 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);
    }
}

sky1231 @ 2017-07-27 17:26:30

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

1

K-Boy LV 10 @ 2009-09-13 17:34:52

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

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

1

火凤凰卡比 LV 10 @ 2009-09-02 13:56:01

天杀的第八个点

0

liuyiah LV 10 @ 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";
}

0

hzszlujy LV 8 @ 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
readln(max,len,n);
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.

0

嗤克 LV 9 @ 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;

}

0

naneux LV 8 @ 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]}

0

llx2192716 LV 8 @ 2009-11-07 13:37:16

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

0

pplong LV 8 @ 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

0

玛维-影之歌 LV 10 @ 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

0

SecretAgent LV 10 @ 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

0

lishunzhi LV 9 @ 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

readln(maxw,len,n);

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]

0

honghaijie LV 9 @ 2009-10-19 12:48:50

0

傻子同学 LV 10 @ 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水题

0

laz LV 10 @ 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

0

Leyni LV 8 @ 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

0

602548825 LV 7 @ 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

0

guojh LV 9 @ 2009-08-11 16:43:28

第八个点要unsigned long

0

xusc_2009 LV 9 @ 2009-08-07 21:14:43

囧第八个点

30行小程序

0

bi1_1 LV 9 @ 2009-08-07 20:30:19

第八个点要int64

题解

69 条题解

车队过桥问题

信息

状态

开发

支持

题解

69 条题解

车队过桥问题

信息

状态

开发

支持

还没有账户？

登录