Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
算法1.判定哪些树桩之间是不能连绳子的 我的方法:枚举树桩i,j和麦田怪圈k 首先,如果i或j在怪圈k的范围内,绳子肯定是不能连的。 然后算出直线(i,j)到怪圈k圆心的距离(这个很简单,叉积乱搞就可以了……),如果大于半径R,就一定不会与k相交了 然后用点积算出k与线段(i,j)的相对位置,如果dot(i,j,k)与dot(j,i,k)异号,那么一定不会与k相交,否则一定会 2.DP求出最优解 我的方法:因为是个凸包,如果用dp[i,j]表示第i个到第j个树桩这一段的最优解的话,有 dp[i,j]=max{dp[i,k]+dp[k,j] i<k<j}+ok[i,j] ok[i,j]为1如果i到j可以连绳子,否则为0 边界情况自己考虑…… 然后dp[1,n]就是答案了 注意:在读入树桩的位置后需要极角排序…… Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator