题解 - Vijos

0

搁浅 LV 9 @ 2010-03-17 09:22:41

你的就是最优的思想了..

0

mauricejoe LV 8 @ 2009-10-26 21:35:58

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

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

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

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

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

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

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

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

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

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

先排个序，再讨论每个数前3个（包括这个数）可能的情况，可以用搜索。。

0

321k LV 9 @ 2009-09-01 12:40:56

首先，容易证明，对于A和C，以及B和D，|A-B|+|C-D|取得最小值仅当A>C且B>D时成立(本题题意要求没有等号)。这就是说两个序列尽量按降序对应才能得到最小值，亦即对于AD,可以通过交换A,C使得结果变小。

因此第一步当然是对两个序列进行降序排序。此时就有a[1]>a[2]>a[3]>...>a[n],b[1]>b[2]>b[3]>...>b[n]。现在问题就可以转化成固定a序列，交换b序列中的一些元素，使得满足题意(即找到一种决策，将a[i]=b[i]的b[i]与其相邻的b[k]交换来使得绝对值和最小)。首先排除边界情况，看一般的i。

若有a[i]!=b[i]则直接计算|a[i]-b[i]|；若a[i]==b[i],那么我们有如下决策:

1.交换b[i]与此时i-1对应的b元素;2.交换b[i]与b;3.交换(b,b),交换b[i]与此时的b，即使最后顺序是b,b[i],b.可以证明，这几种决策囊括了所有决策。

但是，问题来了，第一种决策要依赖b的取值。观察我们的决策并且结合引理，易知b可能取的只能是b,b,b。若b=b，那么交换b[i]与b一定不是最优决策。因为此时b与b或b是逆序，总可以找到一个能与b交换使得和更小。那么，我们可以用f(0,x)表示当前为b[x]，前一个为b[x-1]的最优解，f(1,x)表示...为b[x-2]的...，f(2,x)表示...为b[x-2]的最优解。

综上，有状态转移方程：

1,a[i]==b[i]

f(0,i)=min{abs(a-b[i])+f(i,i+1),abs(a-b)+abs(a[i]-b)+abs(a-b[i])+f(1,i+3),abs(a-b)+abs(a[i]-b)+f(1,i+2)};

f(1,i)=min{abs(a-b[i])+f(2,i+1),abs(a-b)+abs(a[i]-b)+f(1,i+2),abs(a-b)+abs(a[i]-b)+abs(a-b[i])+f(1,i+3)};

f(2,i)=abs(a-b)+abs(a[i]-b)+f(1,i+2);

2,a[i]!=b[i]

f(0,i)=abs(a-b)+f(0,i+1);

f(1,i)=abs(a-b)+f(0,i+1);

f(2,i)=abs(a-b)+f(0,i+1);

这样就不会超时了。但是一定注意边界条件！为了这个我WA了N个。。。

表达能力有限，见谅。

另外，神牛们不要光顾着AC啊，也说说简单方法啊！！

0

voyagec2 LV 10 @ 2009-07-27 10:35:25

Orz cgy

较优化思想

应该是可以证明正确性的

0

boyzkk LV 10 @ 2009-07-08 20:53:27

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

Orz cgy4ever!

写了个状压DP。。手感好了很多。

要用int64。