35 条题解
-
0
kimizhang LV 10 @ 2009-10-03 14:31:50
总算过了。
经过tangky指点才做出来的。
f表示后i个经过调整后第i位是a[i],这个情况比较简单。
f表示后i个经过调整后第i位是a，而a[i]插到第i+1 到 n 当中的某个位置中了。a[i]插进去之后其他位置是不变的。如图
a...a[j],(插入a[i])，a[j+1]..a[n]。
由于a[j+1]到后面的部分的结果已经求出，所以这样多消耗的体力就是|a[j+1]-a[i]|+|a[i]-a[j]|+(|a[j]-a[j-1]|+a[j-1]-a[j-2]|+...|a-a|）;预处理求和，括号里的就等于sum[j]-sum
方程就变成
f:=min{f+|a-a[i]|,f+|a-a[i]|}
f:=min{min{f[j+1,0]+|a[j+1]-a[i]|,f[j+1,1]+|a[j+2]-a[i]|}+|a[i]-a[j]|+sum[j]-sum}.
再次感谢tangky。 -
0
orz教主_tangky LV 7 @ 2009-10-03 11:11:04
好像就我自己有数据吧……
-
0
谢谢给我数据的人，调了一个早上啊，唉
我的算法是N方的
给中心代码吧，不然好惨的，调了一个早上
f[0,0]:=0; f[1,0]:=0;
f[2,0]:=abs(a[1]-a[2]);
f[2,1]:=abs(a[2]-a[1]);
{预处理）
for i:=3 to n do
begin
f:=min(f,f+abs(a-a[i])+abs(a[i]-a));
f:=min(f,f+abs(a[i]-a));
for j:=2 to i-1 do
begin
f:=min(f,f+abs(a-a[i]));
f:=min(f,f+abs(a-a[i])+abs(a[i]-a));
f:=min(f,f+abs(a[i]-a)+abs(a[i]-a)-abs(a-a))
end;
end; -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms我抓狂了 最大值我只定了10000000
改正成1000000000就秒杀了
我无语 从260 掉到210这道dp还是挺有启发性的
f表示第i个数不动的价值
f表示第i个数放到后面去的价值
f:=min(f,f+abs(a-a[i]));
f:=min(f,f[j+1,k]+s-s[j]+abs(a[j+k]-a[i])+abs(a[i]-a[j]));(j>i)
这样要倒着做{s[i] 表示abs（a[i]-a)的前缀合
这样就可以方便计算出i到j区间（没交换）的代价}
画个图就很好理解了 -
0
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms翁芳 算法
-
0
yzl609271536 LV 10 @ 2009-10-03 07:58:54
编译通过...
├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：0ms比赛时出了一点错就90
占了两个名字。。。。
-
0
qyjubriskxp LV 10 @ 2009-10-03 02:23:45
用f[i][j]表示到第i个数前面（包括第i个）连续交换j次消耗最大体力也可
把这题ac率拉低33个百分点不是因为dp写的猥琐，竟然是
fabs(arr[i]-arr)+fabs(arr[i]-arr)
写成了
fabs(arr[i]-arr+fabs(arr[i]-arr))（注意括号）
悲剧啊，以后坚决另写函数 -
0
LV 0 @ 2009-10-02 17:42:39
你们怎么这么快！
kimizhang
LV 10
@ 2009-10-03 14:31:50
