点这里查看
讨论 / 大牛来解释一下为什么不能用贪心
anshantby 2011-07-15 18:22:00
点我顶贴 收藏 删除
每次聚合时将当前最小的数字放在中间，让小数乘的次数少，这样做为什么不可以？
#1 tadus@2008-11-08 01:32:00
回复 删除
DP的入门题啊…

不太解释得清楚…可能是你这个贪心并不是最优的解

你可以找个标程 改下 把合并方式输出来看看

#2 anshantby@2008-11-08 18:35:00
回复 删除
这题过了，只是不知道为什么不能贪心，给各反例数据好吗？
#3 anshantby@2008-11-09 22:22:00
回复 删除
神牛们，有没有反例啊？拜托帮帮忙啦！
#4 barty@2008-11-10 01:13:00
回复 删除
当一个题目的阶段不是及其明显的相互无影响的时候还是别用贪心了……
#5 anshantby@2008-11-13 06:34:00
回复 删除
还是比较相信数据，有数据吗？？？
#6 w122185976@2009-01-14 03:44:00
回复 删除
5 1 10 10 1 5

正确答案是1850，

贪心绝对不超过1000；

#7 seal4@2010-05-11 07:05:00
回复 删除
比如 4 2 1 1 3 和4 3 1 1 2

的答案都是27~

你看看你的

#8 562736924@2011-07-15 06:09:00
回复 删除
答案正确？？？

[quote][url=/Redirect.asp?Act=Reply&DID=3339&RID=14673]原帖[/url]由 [i]seal4[/i] 于 2010-5-11 22:05:00 发表

比如 4 2 1 1 3 和4 3 1 1 2

的答案都是27~

你看看你的[/quote]

应该是81吧

#9 562736924@2011-07-15 06:09:00
回复 删除
回复 地基w122185976 的帖子

我的过了

#10 562736924@2011-07-15 06:15:00
回复 删除
求错！！！

var n,m,i,j,k,la,lb:integer;

z,max:longint;

a:array[0..150]of longint;

begin

read(n);

for i:=1 to n do

read(a[i]);

a[0]:=a[n];

a[n+1]:=a[1];

z:=0;

for m:=n downto 2 do

begin

k:=1001;max:=0;

for i:=1 to m do

if (a[i]<k) then k:=a[i];

for i:=1 to m do

if (a[i]=k)and(a[i-1]*a[i]*a[i+1]>max) then

begin

max:=a[i-1]*a[i]*a[i+1];

la:=i;

end;

z:=z+max;

for i:=la to m do a[i]:=a[i+1];

if la=m then a[0]:=a[m-1];

if la=1 then a[m]:=a[1];

end;

write(z);

end.

查看更多回复
提交回复