题解
1.一定是一部分怪物被水属性咒语打死,另一部分被火属性咒语打死
2.遍历所有“部分”,然后看各部分被水属性咒语打死需要累积多少秒的水咒语
这里用到了背包数组,(1e6·100)也可以?
code
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a[105];
bool dp[1000005]={0};
ll solve()
{
ll w,f,n;
cin>>w>>f>>n;
ll sum=0;
for(int i=1;i<=n;i++ )
{
cin>>a[i];
sum+=a[i];
}
dp[0]=1;
for(int i=1;i<=n;i++)
{
for(int k=sum;k>=a[i];k--)
{
dp[k]=dp[k-a[i]]||dp[k];
}
}
ll ans=2e15;
for(ll i=0;i<=sum;i++)
{
if(dp[i]) ans=min(ans,max(i/w+(i%w!=0),(sum-i)/f+((sum-i)%f!=0)));
dp[i]=0;
}
return ans;
}
int main()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int t;
cin>>t;
while(t--) cout<<solve()<<'\n';
return 0;
}
标签:int,ll,Will,咒语,World,Save,dp
From: https://www.cnblogs.com/pure4knowledge/p/18293817