P4056 [JSOI2009]火星藏宝图

    • 77通过
    • 248提交
  • 题目提供者 njH2Q
  • 评测方式 云端评测
  • 标签 斜率优化 枚举,暴力 桶排 各省省选 2009 江苏
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目背景

    JSOI2009第三轮二试

    题目描述

    在火星游玩多日,jyy偶然地发现了一张藏宝图。根据藏宝图上说法,宝藏被埋藏在一个巨大的湖里的N个岛上(2<=N<=200,000)。为了方便描述,地图把整个湖划分成M行M列(1<=M<=1000),共M*M个小块,并把所有岛按照1...N编了号。第i个岛位于第Xi行Yi列(设其坐标为(Xi,Yi))的格子(Xi,Yi均为整数,并且满足1<=Xi,Yi<=M),岛上藏有价值财富Vi(1<=Vi<=10,000)。湖的左上角(1,1)和右下角(M,M)都有岛,有桥将它们与陆地相连。

    jyy没费多大劲,就找到了那个湖,同时哭笑不得地发现,所谓的财富,是各个岛上出产的珍稀水果。jyy 在左上角的岛的岸边找到了一条小木船,他可以划船到其他岛上去。划船是要消耗体力的,具体地说,等于两岛 Euclidean 距离的平方(即,从(X1,Y1)划船到(X2,Y2)所耗费的体力为(X1-X2)^2+(Y1-Y2)^2个单位)。jyy可以吃水果来恢复体力,吃掉1单位价值的水果能恢复1单位体力。

    现在jyy打算从(1,1)旅行到(M,M),沿途收集珍稀水果。按藏宝图上的提示,jyy 离开一个岛后,就只能去该岛右下方的区域(正下和正右方向也是允许的),否则会遭遇水怪。jyy可以在旅行途中饿一段时间,即体力为负。但抵达终点后,只要身边有足够多的水果,他就会通过吃水果将体力恢复到旅行前的水平。

    jyy想知道,经过一次旅行,他最多能得到多少收益,即jyy收集到的水果总价值-jyy在旅途中花的总体力。(如果吃完所有水果他还饿着,收益就是负数,具体的例子见样例)

    输入输出格式

    输入格式:

    第1行:两个整数N,M。第2..N+1行:每行3个整数,第i+1行的3个整数分别为Xi,Yi,Vi。每个岛的坐标不同。保证存在坐标(1,1)和(M,M)的岛。

    输出格式:

    第1行:输出一个整数,表示最大收益。

    输入输出样例

    输入样例#1: 复制
    4  10 
    1  1  20 
    10 10 10 
    3  5  60 
    5  3  30
    输出样例#1: 复制
    -4

    说明

    20+60+10-((3-1)^2+(5-1)^2)-((10-3)^2+(10-5)^2)=-4

    对20%的数据M<=200,且N<=2,000

    对50%的数据M<=200,且N<=20,000

    对100%的数据M<=1000,且N<=200,000

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。