P3888 [GDOI2014]拯救莫莉斯

    • 55通过
    • 176提交
  • 题目提供者 洛谷OnlineJudge
  • 评测方式 云端评测
  • 标签 动态规划,动规,dp 状态压缩,状压 进制 各省省选 2014 广东 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 256MB

题解

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

    推荐的相关题目 显示

    题目描述

    莫莉斯·乔是圣域里一个叱咤风云的人物,他凭借着自身超强的经济头脑,牢牢控制了圣域的石油市场。

    圣域的地图可以看成是一个n*m的矩阵。每个整数坐标点(x , y)表示一座城市( $1\le x\le n,1\le y\le m$ )。两座城市间相邻的定义为:对于城市(Ax, Ay)和城市(Bx, By),满足 $(Ax - Bx)^2 + (Ay - By)^2 = 1$ 。

    由于圣域的石油贸易总量很大,莫莉斯意识到不能让每笔石油订购单都从同一个油库里发货。为了提高效率,莫莉斯·乔决定在其中一些城市里建造油库,最终使得每一个城市X都满足下列条件之一:

    1.该城市X内建有油库,

    2.某城市Y内建有油库,且城市X与城市Y相邻。

    与地球类似,圣域里不同城市间的地价可能也会有所不同,所以莫莉斯想让完成目标的总花费尽可能少。如果存在多组方案,为了方便管理,莫莉斯会选择建造较少的油库个数。

    输入输出格式

    输入格式:

    第一行两个正整数n,m ( $n \times m \le 50$ 且 $m\le n$ ),表示矩阵的大小。

    接下来一个n行m列的矩阵F, $F_{i, j}$ 表示在城市(i,j)建造油库的代价。

    输出格式:

    输出两个数,建造方案的油库个数和方案的总代价。

    输入输出样例

    输入样例#1: 复制
    3 3
    6 5 4
    1 2 3
    7 8 9
    输出样例#1: 复制
    3 6

    说明

    对于30%数据满足 $n \times m \le 25$ ;

    对于100%数据满足 $n \times m \le 50,0 \le F_{i, j} \le 100000$

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