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 + 二分

发表评论

最新留言

第一次来,支持一个
[***.238.104.143]2022年07月07日 16时13分03秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

最新文章

IEO助推了平台币,但这把火还不足以燃起一个牛市 2019-03-07 07:05:41
巴比特走进香港丨进可攻,退可守,HK如何抢占区块链先机? 2019-03-07 07:05:40
BTC牛熊周期的三大规律与应用 ——冰点展望之一 2019-03-07 07:05:39
EOS一周年重磅!BM:6月将发布EOS.io诞生以来最大新闻 2019-03-07 07:05:39
内含福利 丨关注数字资产安全 KeyShard带来全新解决方案 2019-03-07 07:05:38
专访 | Asic矿机“大军压境”,2019年Grin会诞生“明星矿机”吗? 2019-03-07 07:05:37
为躲避死亡威胁, 只用15步, 这个密码朋克大叔就从世界"消失"了 2019-03-07 07:05:37
摩根溪创始人:资管公司来“搅局”,下一轮牛市规模将“前所未有” 2019-03-07 07:05:36
发行多种稳定币,IBM想要搭建全球支付网络 2019-03-07 07:05:35
一半项目将遭受灭顶之灾?IBM区块链副总裁:量子计算威胁真实可信 2019-03-07 07:05:34
深度 | 还原STO真实生态,剖析合规、融资、流通之困局 2019-03-07 07:05:33
IEO余波未了,BTC试探4000刀,是否已探底?指标显示还早 2019-03-07 07:05:33
平台币走强,交易所“ICO”跃跃欲试,大战即将开打? 2019-03-07 07:05:32
击败黄金!Block.one CEO:不用扩容,比特币也将成为主流价值存储方式 2019-03-07 07:05:31
比特币将再次崛起的5个原因 2019-03-07 07:05:30
重要通知!浙江将举办区块链信息服务备案技术交流会 2019-03-07 07:05:30
预测成瘾的Tom Lee又来了:6个月后牛市回归,你信吗? 2019-03-07 07:05:29
爆料!IBM为银行开发稳定币,跨境支付这块“大蛋糕”怎么分? 2019-03-07 07:05:28
熊市定投,牛市不愁丨链节点AMA集锦 2019-03-07 07:05:27
PlatON数字资产托管服务KeyShard正式上线 2019-03-07 07:05:27