P5322 [BJOI2019]排兵布阵

    • 244通过
    • 369提交
  • 题目提供者 NaCly_Fish
  • 评测方式 云端评测
  • 标签 动态规划,动规,dp 各省省选 2019 北京 O2优化
  • 难度 提高+/省选-
  • 时空限制 1000ms / 512MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    小C正在玩一款排兵布阵的游戏。在游戏中有$n$座城堡,每局对战由两名玩家来争夺这些城堡。每名玩家有$m$名士兵,可以向第$i$座城堡派遣$a_i$名士兵去争夺这个城堡,使得总士兵数不超过$m$。

    如果一名玩家向第$i$座城堡派遣的士兵数严格大于对手派遣士兵数的两倍,那么这名玩家就占领了这座城堡,获得$i$分。

    现在小C即将和其他$s$名玩家两两对战,这$s$场对决的派遣士兵方案必须相同。小C通过某些途径得知了其他$s$名玩家即将使用的策略,他想知道他应该使用什么策略来最大化自己的总分。

    由于答案可能不唯一,你只需要输出小C总分的最大值。

    输入输出格式

    输入格式:

    输入第一行包含三个正整数$s,n,m$,分别表示除了小C以外的玩家人数、城堡数和每名玩家拥有的士兵数。
    接下来$s$行,每行$n$个非负整数,表示一名玩家的策略,其中第$i$个数$a_i$表示这名玩家向第$i$座城堡派遣的士兵数。

    输出格式:

    输出一行一个非负整数,表示小C获得的最大得分。

    输入输出样例

    输入样例#1: 复制
    1 3 10
    2 2 6
    输出样例#1: 复制
    3
    输入样例#2: 复制
    2 3 10
    2 2 6
    0 0 0
    输出样例#2: 复制
    8

    说明

    样例1解释:
    小C的最佳策略为向第$1$座城堡和第$2$座城堡各派遣$5$名士兵。

    样例2解释:
    小C的最佳策略之一为向第$1$座城堡派遣$2$名士兵,向第$2$座城堡派遣$5$名士兵,向第$3$座城堡派遣$1$名士兵。

    数据范围:
    对于$10\%$的数据: $s=1,n \le 3,m \le 10$
    对于$20\%$的数据: $s=1,n \le 10,m \le 100$
    对于$40\%$的数据: $n\le 10,m\le 100$
    对于另外$20\%$的数据: $s=1$
    对于$100\%$的数据:
    $1\le s \le 100$
    $1\le n \le 100$
    $1\le m \le 20000$
    对于每名玩家$a_i \ge 0$,$\sum\limits_{i=1}^n a_i \le m$

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