思路
假设总共耗时是 \(s\) 秒，那么最多可以消灭的总生命值是 \(s\times(w+f)\)。
所以我们可以先求出所有怪物的生命值之和 \(sum\)，那么，至少需要时间 \(t=\lfloor \frac{sum}{w+f} \rfloor\)。
然后我们可以算出用这些时间最多可以用水魔法消灭的生命值为 \(w\times t\)。
那么，我们可以用 dp 求出若干个怪物的生命值之和在小于 \(w\times t\) 的情况下的最大值 \(sum_w\)，那么，在这种情况下，答案就是 \(\max(\lceil \frac {sum_w} w \rceil,\lceil \frac {sum-sum_w} f \rceil)\)。
因为最后答案可能比 \(t\) 大，所以我们可以把所有的可能都求一边，赛时没多想，随手遍历了 \(t\sim t+10\) 居然可以 AC，就没多想去看下一题了（主要是当时时间不多了），好像被 hack 了。
AC code
#include<bits/stdc++.h>
using namespace std;
long long T,w,f,n,a[105],dp[1000005],sum,ans,res;
int main()
{
scanf("%lld",&T);
while(T--)
{
scanf("%lld%lld%lld",&w,&f,&n),sum=0,ans=0x3f3f3f3f3f3f3f3f;
for(long long i=1;i<=n;++i) scanf("%lld",&a[i]),sum+=a[i];
if(sum<w||sum<f){printf("1\n");continue;}
long long s=ceil(1.0*sum/(w+f));
for(long long k=s;k<=s+10;++k)
{
memset(dp,0,sizeof(dp));
for(long long i=1;i<=n;i++) for(long long j=k*w;j>=a[i];j--) dp[j]=max(dp[j],dp[j-a[i]]+a[i]);
res=max((long long)ceil(1.0*dp[k*w]/w),(long long)ceil(1.0*(sum-dp[k*w])/f));
if(res<ans) ans=res;
//else break;
}
printf("%lld\n",ans);
}
}
比赛水过去就水过去了，比完了就要思考正确的解法了。
第一种优化方式是减少 dp 次数，也就是枚举 \(j\) 的时候只枚举新增的那部分，但是时间复杂度仍然比较高。
所以我们换种思路，既然 dp 是为了得到若干个数加起来小于某个值的最大值，那么我们可以预处理出所有的可能的和，然后在来枚举得到答案不就行了？
那么，如何得到所有的可能的和呢？嗯，还是 dp，如下：
for(int i=1;i<=n;++i) for(int j=sum;j>=a[i];--j) dp[j]=dp[j]||dp[j-a[i]];
然后枚举所有可能的情况，然后算出答案即可。
for(int i=0;i<=sum;++i)if(dp[i]) ans=min(ans,max((long long)ceil(1.0*i/w),(long long)ceil(1.0*(sum-i)/f)));
完整代码就不放了。