本文共 1515 字，大约阅读时间需要 5 分钟。

马拉松比赛

时间限制: 1 Sec 内存限制: 128 MB

题目描述

明明同学参加马拉松比赛，马拉松全程包括N个检查点(3<=N<=500)，明明同学要按顺序通过，检查点1在起始位置、检查点N是终点。明明同学应该通过所有这些检查点,但是他最近比较累,他决定跳过K个检查点(K<N-1)以尽可能缩短总路程。但显然，他不能跳过检查点1或N，因为这太容易被发现了！ 请帮助明明同学找到他长跑的最短距离,如果他可以跳过K个检查点的话。 如果两个检查点的位置分别为(x1,y1)和(x2,y2)，则它们的距离为|x1-x2|+|y1-y2|。 输入 第一行两个用空格隔开的整数N和K。 接下来的N行每个包含两个空格分隔的整数,x和y,代表一个检查点(-1000<=x<=1000,-1000<=y<=1000)。注意,可能几个检查点会在同一物理位置。明明跳过这样的检查站时,他一次只能跳过一个检查站。 输出 一个正整数，表示他能跑的最短距离。 样例输入 Copy 5 2 0 0 8 3 1 1 10 -5 2 2 样例输出 Copy 4

数据比较小，比较简单的做法就是dp了，直接三重循环套上，可能还有更好的吧，但是太笨了想不出来。

f [ i ] [ j ] 中 i 表示枚举到的点位置，j 表示该点剩余的可以跳过点的数量。 第一层循环当然是枚举点的位置了，第二层循环枚举该点剩余的可以跳过点的数量，第三层枚举要跳过的点，注意判断一下转移过去是否大于n即可。 状态转移的话直接看代码比较清楚。。毕竟变量比较多。。

做题注意再一下范围就好了，一个数组开小了一直TLE，一个数组开小了RE，就离谱。

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
      
     
    
   

转载地址：https://blog.csdn.net/DaNIelLAk/article/details/105717762 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！