我晕死了....

没看清楚题目....以为不按顺序......想了n久....看了题解才发现.....

有顺序就简单多了

结果呈秒杀状.....

编译通过...

├ 测试数据 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

秒杀！AC100！

编译通过...

├ 测试数据 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

简单DP

别鄙视垃圾啊.华二第一神牛日文...第2大牛方睿...

“max,len,w,v不超过32位有符号整数类型的最大值，且为整数”

但中间计算过程可能会超出 int32_t 的范围而溢出，变成负数（第八组数据）

使用 unsigned 就行了（C/C++）

华二最强 xuke

注意INT64 啊！

读入数据都要INT64！

。。。。。。。。。。

考试因此WA了一个点。

用看球的巴士那题的思想做

题目只要求按顺序分组,大大降低了题目难度..不然就又是一个多重背包问题...

由于题目没给出数据的范围,因此不可能将速度或者重量作为DP方程的一种状态...

因此想到F一维方程

F=MIN([F[J]+LEN/Vmin);J=1..I-1,Vmin=MIN(V[J+1]..V);

若W[J]+..W>MAX 则退出里层循环

├ 测试数据 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

先用递推预处理，然后dp，复杂度O(n^2)

重量可能超过longint,可以对此做特殊处理(比如设为-max),然后在dp时判断下就可以了。

当然也可以int64

用int64

编译通过...

├ 测试数据 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

简单的DP

要注意的一点是：

输出的单位是MIN！！！

记住！

好在我看到了，不然都不知道要调多久！

所以，又学到东西了，

审题不要因为题目简单而忽略了细节！！

分组需要取连续的一组。。。。。。

跟解题有点像

program p1355;

const maxn=1000;

var ton,len :extended;

n :longint;

w,v,f :array[0..maxn] of extended;

procedure init;

var i:longint;

begin

readln(ton,len,n);

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

end;

procedure dymic;

var i,j :longint;

t,minv :extended;

begin

f[0]:=0;

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

for i:=2 to n do

begin

f[i]:=maxlongint;

t:=0; minv:=maxlongint;

for j:=i downto 1 do

begin

t:=t+w[j];

if v[j]ton then break;

if f[j-1]+len/minv

简单的DP，不要做无用功

谁能讲讲思路啊！

我的程序是N的3次方的 加了一些小小的优化过了 不知各位0秒A的大牛怎么过的？？

第100个ac...

不过也出现与楼下Fengyunfly大牛相同的状况，不解~~

编译通过...

├ 测试数据 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

( 2008-7-19 15:30:29 )