Problem 4070 --C 石子游戏4070: C 石子游戏
| Time Limit |
$1$ 秒/Second(s) |
Memory Limit |
$512$ 兆字节/Megabyte(s) |
| 提交总数 |
$3$ |
正确数量 |
$0$ |
"
| 裁判形式 |
标准裁判/Standard Judge |
我的状态 |
尚未尝试 |
| 难度 |
|
分类标签 |
|
当前分类(单击移除)：
单击选择分类：
Luca和Yuki打算玩取石子游戏。
一共有n颗石子，每颗石子都有两个属性bi，和wi。她们还约定了一个函数c(m)。在此基础上，游戏的流程如下：
1．开始时把所有石子置入场内，双方初始分数均为0。
2.Luca从场上石子中移除任意个（不可以移除0个） 。移除后，Luca获得∑wi分。（求和等计算均针对仍留在场上的石子，下同）
3.Yuki从场上石子中移除任意个（可以移除0个）。移除后，设场上还剩下m个石子，如果m∑bi<c(m) ∑wi成立，Yuki获得m∑wi 分。然后无论Yuki是否获得了分数，均将Yuki移除的石子移回。
4．如果场上已经没有石子，游戏结束；否则回到第2步。
Luca的目标是在最小化Yuki的分数的前提下最大化自己的分数，而Yuki的目标是最大化自己的分数。如果Luca和Yuki都按各自的最优策略决策，聪明的你能计算出她们的最后得分吗？
输入的第1行包含1个整数n(1≤ n ≤22)，表示石子的数量。
接下来1行，包含n个整数，其中第i个表示bi(1≤bi≤10000)。
接下来1行，包含n个整数，其中第i个表示wi(1 ≤ wi ≤ 10000)。
接下来1行，包含n个整数，其中第i个表示c(i)(|c(i)|≤ 1000）的值。约定c(0)=0。
输出一行2个整数，依次表示双方均按最优策略行动时Luca和Yuki的最终得分。
4
1 2 3 4
4 3 2 1
1 2 3 4
第1轮：Luca移除1号和2号石子（按输入顺序编号），得到w3+W4=3分；可以证明，该局面下Yuki无论如何行动均无法得分。注意此时Luca若移除4号石子将得到更高的总分，但Luca更希望最小化Yuki的分数（见题目描述），因此这里她不会选择移除4号石子。
第2轮：Luca移除4号石子，得到w3=2分；Yuki仍然无法得分。
第3轮：Luca移除3号石子，游戏结束，Luca最终得分为5分，Yuki最终得分为0分。
| 本题记录 |
用 户（点击查看用户） |
运行号（点击购买题解） |
时 间 |
| 算法最快[$ $ms]
|
|
|
|
| 内存最少[$ $KB]
|
|
|
|
| 第一AC |
|
|
|
| 第一挑战 |
Accer
|
1095772 |
2024-04-16 20:40:33 |