upc 马拉松比赛 dp-白红宇的个人博客

upc 马拉松比赛 dp

发布日期：2021-09-25 23:57:36 浏览次数：0 分类：技术文章

本文共 1519 字，大约阅读时间需要 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
       #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #define X first#define Y secondusing namespace std;typedef long long LL;typedef pair
               
                 PII;const int N=510,mod=1e9+7,INF=0x3f3f3f3f;const double eps=1e-6;int n,k;PII p[N];LL f[N][N];int get_dis(int a,int b){    
                
PII x=p[a],y=p[b];
                
return abs(x.X-y.X)+abs(x.Y-y.Y);}int main(){    //
                
ios::sync_with_stdio(false);//
                
cin.tie(0);
                
scanf("%d%d",&n,&k);
                
for(int i=1;i<=n;i++)
                
{    
                
int x,y;
                
scanf("%d%d",&x,&y);
                
p[i]={    x,y};
                
}
                
memset(f,0x3f,sizeof f);
                
for(int i=0;i<=n;i++)
                
f[1][i]=0;
                
for(int i=1;i<=n;i++)//枚举位置 
                
for(int j=0;j<=k;j++)//枚举剩余的 
                
for(int t=0;t<=j&&i+t+1<=n;t++)//枚举要用的 
                
f[i+t+1][j-t]=min(f[i+t+1][j-t],f[i][j]+get_dis(i,i+t+1));
                
printf("%lld\n",f[n][0]);
                
return 0;}

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

上一篇：最后一次新生赛 B+C+D

下一篇：upc 地球发动机线性dp + 二分

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

最新文章