bzoj 4745: [Usaco2016 Dec]Cow Checklist DP

题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id=4745


题目大意:有A、B两类点在一个二维平面上,A类的点有n个,B类的点有m个,要求从A类点的第1个开始走,走到第n个结束,所有点必须有序(编号从小到大)但不用连续地经过一次。求在满足条件的情况下,最短的所经过的路径的欧几里得距离平方和是多少。


dp[i][j][0/1]表示A类点走到了第i个,B类点走到了第j个,当前所在的点的类型是A(0)或B(1)

然后大力n^2 dp就好了

 

发表评论