A1788 | 我心中珍藏的游戏
时间限制1s
内存限制128MB
通过 / 提交0/0
题目描述
Macw最喜欢的游戏莫过于是“Battle Eggman”了。而现在，这款游戏更新了新的技能对战模式。在这个模式中，Macw作为游戏的玩家可以发动 $n$ 个技能。
游戏的机制是这样子的，玩家可以任意选择多个攻击加成。一个加成形如 $E_{v1, v2}$。表示如果一位玩家发动了技能v1，而他又发动了技能v2，那么他就可以额外获得 $E_{v1, v2}$ 点伤害。相反也是如此。也就是说 $E_{v1, v2} = E_{v2, v1}$。
聪明的Macw想考考你，Macw他最多可以额外获得多少点的攻击伤害。
游戏的机制是这样子的，玩家可以任意选择多个攻击加成。一个加成形如 $E_{v1, v2}$。表示如果一位玩家发动了技能v1，而他又发动了技能v2，那么他就可以额外获得 $E_{v1, v2}$ 点伤害。相反也是如此。也就是说 $E_{v1, v2} = E_{v2, v1}$。
聪明的Macw想考考你，Macw他最多可以额外获得多少点的攻击伤害。
输入格式
输入包含 $n+1$ 行。
第一行输入一个整数 $n$，代表Macw可以发动n个技能。
接下来的$n$行，每一行$n$个数字。可以将这些输入看作为是一个$n*n$的矩阵。
矩阵的第 $i$ 行第 $j$ 列就是发动第 $i$ 个攻击后再发动第$j$个攻击后可以获得的攻击加成。
例如，矩阵的 $(1, 3) = 5$，若Macw使用该加成表示Macw在发动完第1个技能后，再发动第3个技能的时候就可以获得5点攻击加成。
输入数据保证当 $v1=v2$ 时，$E_{v1, v2}=0$。
如果 $E_{v1, v2}=0$，该攻击加成无效或不存在。
第一行输入一个整数 $n$，代表Macw可以发动n个技能。
接下来的$n$行，每一行$n$个数字。可以将这些输入看作为是一个$n*n$的矩阵。
矩阵的第 $i$ 行第 $j$ 列就是发动第 $i$ 个攻击后再发动第$j$个攻击后可以获得的攻击加成。
例如，矩阵的 $(1, 3) = 5$，若Macw使用该加成表示Macw在发动完第1个技能后，再发动第3个技能的时候就可以获得5点攻击加成。
输入数据保证当 $v1=v2$ 时，$E_{v1, v2}=0$。
如果 $E_{v1, v2}=0$，该攻击加成无效或不存在。
输出格式
输出一行一个整数，表示Macw他最多可以额外获得多少点的攻击伤害。
输入输出样例
输入 #1
3 0 3 5 3 0 10 5 10 0
输出 #1
15
输入 #2
5 0 46 28 50 12 46 0 2 25 44 28 2 0 21 42 50 25 21 0 23 12 44 42 23 0
输出 #2
182
数据范围：
对于100%的数据，保证 $1 \leq n \leq 800$。
对于100%的数据，保证 $0 \leq E_{v1, v2} \leq 1000$。
对于100%的数据，保证可以使用 $32$ 位带符号整型存储。
样例解释：
对于第一个样例：
游戏一共有6个技能加成：
第一对加成：$E_{1, 2} = E_{2, 1} = 3$。
第二对加成：$E_{1, 3} = E_{3, 1} = 5$。
第三对加成：$E_{2, 3} = E_{3, 2} = 10$。
Macw可以选择先发动技能1再发动技能3，使用第二对加成获得5点攻击加成。
之后Macw再发动技能2，使用第三对加成即可获得10点攻击加成。
因此Macw可以获得的最大攻击加成为$5 + 10 = 15$。
对于第二个样例，一个可行操作方案如下：
使用技能4 -> 使用技能3 -> 使用加成$E_{4, 1}$ -> 使用技能1 -> 使用加成$E_{3, 5}$ -> 使用技能 5 -> 使用加成$E_{1, 2}$ -> 同时使用加成$E_{4, 2}$ -> 使用技能2。
对于100%的数据，保证 $1 \leq n \leq 800$。
对于100%的数据，保证 $0 \leq E_{v1, v2} \leq 1000$。
对于100%的数据，保证可以使用 $32$ 位带符号整型存储。
样例解释：
对于第一个样例：
游戏一共有6个技能加成：
第一对加成：$E_{1, 2} = E_{2, 1} = 3$。
第二对加成：$E_{1, 3} = E_{3, 1} = 5$。
第三对加成：$E_{2, 3} = E_{3, 2} = 10$。
Macw可以选择先发动技能1再发动技能3，使用第二对加成获得5点攻击加成。
之后Macw再发动技能2，使用第三对加成即可获得10点攻击加成。
因此Macw可以获得的最大攻击加成为$5 + 10 = 15$。
对于第二个样例，一个可行操作方案如下：
使用技能4 -> 使用技能3 -> 使用加成$E_{4, 1}$ -> 使用技能1 -> 使用加成$E_{3, 5}$ -> 使用技能 5 -> 使用加成$E_{1, 2}$ -> 同时使用加成$E_{4, 2}$ -> 使用技能2。
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？