...汗。。弄了一个早上，，改了无数次（辛亏没有交），，

那家伙不是来破坏环境的，只是来拿钱的。。不一定要每天都毁灭一棵树的。。

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

不能一次AC，遗憾啊

谁能解释为什么要排序啊?

为什么最优解不在f[k]里面啊........

我可怜的通过率啊.....

郁闷~~~~

把readln(n,k)

写前面就全零分..

├ 测试数据 01：答案错误...程序输出比正确答案长

├ 测试数据 02：答案错误...程序输出比正确答案长

├ 测试数据 03：答案错误...程序输出比正确答案长

├ 测试数据 04：答案错误...程序输出比正确答案长

├ 测试数据 05：答案错误...程序输出比正确答案长

├ 测试数据 06：答案错误...程序输出比正确答案长

├ 测试数据 07：答案错误...程序输出比正确答案长

├ 测试数据 08：答案错误...程序输出比正确答案长

├ 测试数据 09：答案错误...程序输出比正确答案长

├ 测试数据 10：答案错误...程序输出比正确答案长

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

Unaccepted 有效得分：0 有效耗时：0ms

写在后面就满分..

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

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

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

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

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

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

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

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

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

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

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

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

zju 月赛题。。

排序+背包

f[0]:=0;

for i:= 1 to n do

for j:= k downto 1 do

if f[j-1] + m[i] - b[i] * ( j - 1 ) > f[j] then

begin

f[j] := f[j-1] + m[i] - b[i] * ( j - 1 ) ;

if f[j] > max then max:=f[j];

end;

Hint 那里money怎么就变成果子了...

将树按递减量降序排序，即保证贵的先砍。

这个应该可以通过调整法证明。

之后就是背包问题：

F前i树砍j棵的最大价值是多少。

答案是：

Ans = Max{F[n,j]|1

var v,n,k:longint;

m,b:array[1..1000] of longint;

procedure ls(q,w:longint);

var i,j,max,p:longint;

f:array[1..1000,1..1000] of longint;

begin

p:=0;

for i:=1 to q do for j:=1 to w do f:=0;

for i:=1 to q do

for j:=1 to w do

begin

max:=0;

if m[i]-b[i]*(j-1)>0 then max:=f+m[i]-b[i]*(j-1) else max:=0;

if f>max then max:=f;

if f>max then max:=f;

f:=max;

if f>p then p:=f;

end;

writeln(p);

end;

begin

readln(n,k);

while (n0) or (k0) do

begin

fillchar(m,sizeof(m),0);

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

for v:=1 to n do read(m[v]);

readln;

for v:=1 to n do read(b[v]);

ls(n,k);

readln(n,k);

end;

readln;

end.

哪错了，为什么会堆栈溢出

我觉得还是有难度的 要按树和时间两个因素来划分阶段 不过大牛的证明相当重要！！(其实本质还是像01背包，砍或不砍两种情况）

关于时间变化的东西，要根据变化率排序 要注意砍完树得到的金币不会出现负值 如果每天掉的金币数不同怎么做呢？？

一共只有两个可能 f表示第j天砍了前i棵树,有

f=max( f+a[i]-b[i]*(j-1), f) 如果 a[i]-b[i]*(j-1)

关键在于按消耗从大到小排序！这样可保证解有可能最优！

for i:=1 to n do

for j:=1 to k do

begin

if m[i]-b[i]*(j-1)>0

then max:=f+m[i]-b[i]*(j-1)

else max:=0;

if f>max

then max:=f;

if f>max

then max:=f;

f:=max;

end;

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

证明单调才是DP本质！！

膜拜董华星大牛的单调性》》》》》》

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

easy...

如果k>=n就一定可以贪心

如果k

这题好像可以用贪心呀

不过我还是用DP,先排序

f表示前i个果子用j天拿到的最大值

f:=max(f,f,f+p);

( if a[i]

方程自己想,不是很难拉,先把消耗排序,从大到小,然后就是DP拉,最后记得是取

f里的最大值!!!

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

将消耗的多少排序再来一次dp.

其实我们不应该把题目看难了……

注意：此题不需考虑摘果子，只需考虑砍树即可！！

法克！

最后要找一遍最大的！

地板,DP题,在某牛指导下委琐的过了