这个题目和题面都很一言难尽
我们发现保持自己的自信值非负和对大佬造成伤害没有关联，我们可以先\(dp\)出自己最多可以活几天
\(f[i][j]\)为前\(i\)天自信值为\(j\)时最多能怼大佬多少天
\(f[i][j-a[i]]=max(f[i-1][j]+1,f[i][j-a[i])\)这个是不吃血包的情况
\(f[i][j-a[i]+w[i]]=max(f[i-1][j],f[i][j-a[i]+w[i]])\)这个是吃血包的情况
嗯，然后我们可以得出最多能拿出多少天怼大佬，假设为\(day\)天
然后再考虑怼大佬的问题，先大力\(bfs+hash\)求出所有能对大佬用嘲讽造成伤害的天数和攻击力的组合
假设所有组合数是\(k\)
不用嘲讽和只用一次嘲讽的情况很好判，下面讨论用两次嘲讽
假设两次嘲讽伤害是\(f1,f2\)，天数是\(d1,d2\)，那么需要满足
\(f1+f2<=c[i],d1+d2<=day,f1+f2+day-d1-d2>=c[i]\)
我们会发现满足第三个条件时必定满足第二个条件，可以忽略第二个
大力枚举\(O(mk^2)\)，一脸不能过的杨子
\(O(mk)\)好像一脸能过的亚子，想想怎么优化
我们可以考虑，对所有组合按\(f\)排序
第一个条件\(f1,f2\)，可以弄两个指针，一个从小往大，一个从大往小
第三个条件，我们移一下项得到\(f1+day-d1>=c[i]+d2-f2\)
那么我们在移动第二个指针的时候记录一下最小的\(d2-f2\)，然后对于每个\(f1,d1\)判断条件是否成立
原文：https://www.cnblogs.com/knife-rose/p/12623970.html