打膈膜 【NOIP2016提高A组模拟10.15】

题目

样例输入：

3 4
2 4 4

样例输出：

6

数据范围：

剖解题目

。。。。。。

思路

第一眼就是觉得，肯定是dp题，然而发现好难搞，然后就贪心的想了想（其实是打了太多游戏所得到的经验），明显觉得群伤更优于重击（多人时），然而不会证，就没有打。

解法

首先很明显一定是先放技能更好。(^o^)/~。
50%：首先怪物生命从小到大排个序，我们一定得先在前面把技能放了。直接枚举放哪个技能就好了。这里一个小剪枝优化：就是当前怪物剩下1点血后，就必然放群攻。
对于技能，不需要暴力修改。
对于群攻，用一个数组记录释放过次数。
对于重击，只要少加一回合答案即可。
时间$O(n log n+2^m)$.

80%:dp。
设 f[i][c][z][q] 表示现在有 i 点魔法值，正在打第 c 个怪（前 c−1 个 都打完了），对这个怪用了 z 次重击，一共用过 q 次群攻，从现在到结束最少要多少生命。 可以得到 f[i][n + 1][z][q] = 0，答案是 f[m][1][0][0]。 当前怪的生命值是 hi −2z−q，如果选择重击，那么从 f[i−1][c][z + 1][q] 转移，如果选择群攻，从 f[i−1][c][z][q + 1] 转移。 时间复杂度 O(nlogn + nm2)，空间可以用滚动数组优化到 O(nm)。

100%（1）：注意到一些优化：一是快速找到当前怪物被打死后，下一个怪是谁；二是魔法值用完后要能 快速算答案。 这个时候总状态数不会很多（2z + q 6 hi,i + z + q 6 m…），上界是 O(m^4)，实际上几乎是 O(m^3) 的。 写哈希或用 std::map 进行记忆化搜索，时间复杂度 O(nlogn + m^3 logm)

100%(2)：打过游戏，知道群攻更赚。
当在场上怪物的人数超过2个时，就用群攻。等于2时随意。等于1时用重击。
这明显正确。

代码

#include<cstdio>
#include<algorithm>
#include<cstring>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define ll long longusing namespace std;const int maxn=1e5+5;
int a[maxn],n,m,num;
ll ans,now;int main()
{freopen("game.in","r",stdin);freopen("game.out","w",stdout);scanf("%d%d",&n,&m);fo(i,1,n) scanf("%d",&a[i]);sort(a+1,a+n+1);int i=1; now=n; while (m){if (a[i]-num==1||now>2) ++num;else if (a[i]-num>1||now<=2) a[i]-=2;--m;while (a[i]-num==0) ++i,now--;ans+=now;}ans=ans-now;fo(h,i,n) ans=ans+(ll)(n-h+1)*(ll)(a[h]-num);printf("%lld",ans);
}