SRM1154--Topcoder初体验

<br >
在frank_c1的帮助下，辣鸡Xiejiadong也开始做Topcoder辣......
<br >
这算是一次Topcoder的初体验吧....

具体的Topcoder应该怎么操作，戳这里
<br >

<br >

显然，我们要求一个(x),使得(|x-a|+|x-b|+|x-c|+|x-d|)最小

根据绝对值的性质，分别让(x)取(a,b,c,d)，求的最小值即可

考虑字符串(s)中的一位，只能来源于前面几位

对于字符串(s)和字符串(t)不相同的位置，要改相同，当且仅当字符串(s)这个位置之前有字符串(t)的当前位置的这个字符

直接扫一遍即可

用(f[i][j][k])表示，第(i)棵树，移除第(j)条边，其中第一棵树移除了第(k)条边的方案数

考虑直接(O(n^2))枚举暴力转移

判断是否仍然构成的树的方法是，首先，他们必须是一个联通块，用并查集解决_{；其次，必须每个点都有被提及（现在发现这个条件是多余的，包含在前者中）}

至于为什么(dp)需要三维，因为，最后一棵树的边要移动到第一棵树，所以最后根据第(m-1)棵树的方案数，直接验证累加即可