题解 P2507 【[SCOI2008]配对】

浅色调 · 2018-06-01 18:56:32 · 题解

Solution：

　　这个贪心神了。。。～

　　我们首先考虑没有限制条件，即不需要满足配对时a_i\neq b_i这个条件，那么很容易想到贪心的思路，直接对a,b从小到大排一遍序，然后累加同项之差相减的绝对值即可。

　　但是现在有了限制，各种方法骚，没有刚过，感觉完全不可做。

　　后面仔细看题，发现一个超级重要的条件，保证a中数各不相同，b中数各不相同。

　　那么就好搞了，我们先对a,b各自从小到大排一遍序，然后进行以下操作：

　　首先考虑输出-1的情况：很显然只有当序列长度为1且a_1=b_1时无解，因为当n\geq 2时，由于数各不相同，那么同一个数a,b中顶多各自出现一次，我们就可以用后面的数和前面的数配对（显然一定不会相等）。

　　其次，当有解时，我们贪心的想到，因为每个数顶多在a,b中各出现一次，所以当某次a_i=b_i时，则a_i\neq b_{i-1}且a_i\neq b_{i+1}（b_i同理），于是我们可以让其和a_{i-1},b_{i-1}或者a_{i+1},b_{i+1}搭配，或者三个互相搭配，在中间取最小值就好了。（即使这三对数，每对相同，但由于a,b中数各自不同，那么这三对数一定可以搭配出两两不同的情况）

　　那么由于前两次需要判断边界，且i+1可能越界。于是将过程改为a_i,a_{i-1},a_{i-2}三个比较取最小值（都一样的）。

　　排序后，求解的整个过程是线性的，于是用DP的思想来转移实现。

　　定义状态f[i]表示前i个配对能得到的最小值，因为每次转移是三个比较，则初值f[1]=|a_1-b_1|，f[2]=min(f[1]+|a2-b2|,|a1-b2|+|a2-b1|)（注意当配对的两个数相等时，将其算出的值赋为inf）。

　　那么不难得出状态转移方程：

　　f[i]=f[i-1]+|a_i-b_i|（直接配对a_i和b_i）

　　f[i]=min(f[i],f[i-2]+|a_i-b_{i-1}|+|a_{i-1}-b_i|)（i和i-1配对）

　　f[i]=min(f[i],f[i-3]+|a_i-b_{i-2}|+|a_{i-1}-b_{i-1}|+|a_{i-2}-b_i|)（三个配对时，让i和i-2配对）

　　f[i]=min(f[i],f[i-3]+|a_i-b_{i-2}|+|a_{i-1}-b_i|+|a_{i+1}-b_{i-1}|)（三个配对时，a,b两两匹配的一种情况）

　　f[i]=min(f[i],f[i-3]+|a_i-b_{i-1}|+|a_{i-1}-b_{i-2}|+|a_{i+1}-b_i|)（三个配对时，a,b两两匹配的另一种情况）

　　最后目标状态f[n]就是答案。