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\)棵树的方案数，直接验证累加即可

巴特西