HBC232178[HNOI2011]卡农,动态规划,容斥原理与鸽巢原理,排列组合哦~唔西迪西小姐~题解 （你能告诉唔西迪西她最多得几分吗）

想要检验自己的编程水平？来试试全网最全C++题库，让您在挑战中不断进步。

n个格子组成，每个格子要么是冰之格，要么是火之格，唔西迪西刚开始可以选择从迷宫中任意一个开始走，走到第。如果唔西迪西当前在冰之格，那么她可以选择一个编号大于当前格子的冰之格，跳到那里，如果唔西迪西当前在火之格，那么她可以选择一个编号大于当前格子的火之格，跳到那里，如果唔西迪西目前没有格子可以走，那么结束，同时，即使存在可以跳过去的格子，唔西迪西也可以选择在任意时刻结束。

唔西迪西现在正处在一个冰火迷宫中，迷宫由  n n 个格子组成，每个格子要么是冰之格，要么是火之格，唔西迪西刚开始可以选择从迷宫中任意一个开始走，走到第  i i 个位置时会得到值为  a_i a i ​  的积分。（注意：唔西迪西也可以选择一个格子都不走） 如果唔西迪西当前在冰之格，那么她可以选择一个编号大于当前格子的冰之格，跳到那里。如果唔西迪西当前在火之格，那么她可以选择一个编号大于当前格子的火之格，跳到那里。如果唔西迪西目前没有格子可以走，那么结束。同时，即使存在可以跳过去的格子，唔西迪西也可以选择在任意时刻结束。 唔西迪西想最大化她的得分，于是她学会了一个超能力，她能在比赛开始的时候改变最多  m m 个格子的状态，即将一个格子从冰之格变成火之格或从火之格变成冰之格，改变第  i i 个格子的状态会让唔西迪西的得分减少  p_i p i ​  。（唔西迪西改变格子的状态后才开始挑选起点开始行动，也就是说，得分分成两部分，一部分是改变格子状态的得分，一部分是走格子的得分） 你能告诉唔西迪西她最多得几分吗

不断挑战自我，才能突破极限！全网最全C++题库，让您在编程道路上越走越远。

标签： HBC232178[HNOI2011]卡农 动态规划 容斥原理与鸽巢原理 排列组合哦~唔西迪西小姐~题解