NC19817. 萌新拆塔
描述
输入描述
第一行一个整数T(T≤ 100)，表示数据组数。
每组数据第一行四个整数，表示h,a,d,m(1≤ h≤ 109, 1≤ a,d≤ 105,0≤ m≤ 105)，表示勇士的初始血量，攻击，防御与魔防。
接下来一行一个数字n(n ≤ 14)，表示怪的数量。
接下来n行，每行八个数字，表示H,A,D,S,ap,dp,mp,hp(1≤ H,A,D≤ 105, 0≤ S≤ 15, 0≤ ap,dp,mp≤ 104, 1≤ hp≤ 109)，表示怪物的血量，攻击，防御，属性，以及怪物守的宝石能增加的攻击，防御，魔防和血量。
怪物的属性由二进制表示，如果有先攻属性，那么S增加1，魔攻增加2，二连击增加4，模仿增加8。
接下来一行一个整数k(0≤ k≤ 100)，表示有k条规则。接下来k行，每行两个正整数u,v (1≤ u<v>保证只有5组数据有n≥ 12。</v>
输出描述
对于每组数据输出一行，表示杀完所有的怪剩下的最多血量。如果无法清完所有怪，那么输出-1。
示例1
输入:
1 20 2 2 0 10 2 2 0 0 2 0 0 80 18 8 0 0 0 0 0 20 40 6 1 0 2 0 0 40 42 7 3 0 1 0 0 40 10 10 5 0 0 2 0 40 25 5 0 0 0 0 0 20 35 4 1 0 0 1 0 20 60 7 2 0 1 1 0 40 32 8 2 0 0 0 0 60 160 15 0 0 0 0 0 0 9 1 2 2 3 1 4 4 5 1 6 6 7 6 8 7 9
输出:
1
C++14(g++5.4) 解法, 执行用时: 1301ms, 内存消耗: 77156K, 提交时间: 2018-10-05 19:46:57
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define lb(x) (x&-x)
#define gc() getchar()
typedef long long LL;
const int N=(1<<14)+5,M=5e6;
int pw[16],bit[N],ok[16],sap[N],sdp[N],smp[N],s1[M],s2[M];
LL f[M];
struct Monster
{
int H,A,D,S,ap,dp,mp,hp;
}A[N];
inline int read()
{
int now=0;register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now;
}
LL Combat(Monster mon,LL hp,int atk,int def,int mdf)
{
if(mon.S&8) mon.A=atk, mon.D=def;
if(mon.S&2) def=0;
if(atk<=mon.D) return 0ll;
int dps=atk-mon.D, mon_dps=mon.A<=def?0:mon.A-def;
int tm=(mon.S&4)?2:1;
LL hpbef=hp; hp+=mdf;
if(mon.S&1) hp-=mon_dps*tm;
hp-=1ll*mon_dps*tm*((mon.H+dps-1)/dps-1);
return hp>hpbef?hpbef:hp;
}
int main()
{
// freopen("A.in","r",stdin);
pw[0]=1;
for(int i=1; i<=14; ++i) pw[i]=pw[i-1]*3;
for(int i=1; i<=14; ++i) bit[1<<i]=i;
for(int T=read(); T--; )
{
memset(ok,0,sizeof ok), memset(f,0,sizeof f);
int Hp=read(), Atk=read(), Def=read(), Mdf=read();
int n=read();
for(int i=0; i<n; ++i) A[i]=(Monster){read(),read(),read(),read(),read(),read(),read(),read()};
for(int K=read(); K--; ) ok[read()-1]|=1<<(read()-1);
int tot=(1<<n)-1;
for(int s=0; s<=tot; ++s)
{
sap[s]=Atk, sdp[s]=Def, smp[s]=Mdf;
for(int i=0; i<n; ++i) if(s>>i&1) sap[s]+=A[i].ap, sdp[s]+=A[i].dp, smp[s]+=A[i].mp;
}
int lim=pw[n]-1; f[0]=Hp;
for(int s=0; s<lim; ++s)
{
if(!f[s]) continue;//!
int S1=s1[s], S2=s2[s];
for(int i=S1^tot,j; i; i^=lb(i))
{
j=bit[lb(i)];
if((S1&ok[j])!=ok[j]) continue;
f[s+pw[j]]=std::max(f[s+pw[j]],Combat(A[j],f[s],sap[S2],sdp[S2],smp[S2]));
s1[s+pw[j]]=S1|(1<<j), s2[s+pw[j]]=S2;
}
for(int i=S1^S2,j; i; i^=lb(i))
{
j=bit[lb(i)];
f[s+pw[j]]=std::max(f[s+pw[j]],f[s]+A[j].hp);
s1[s+pw[j]]=S1, s2[s+pw[j]]=S2|(1<<j);
}
}
printf("%lld\n",f[lim]?f[lim]:-1ll);
}
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 1210ms, 内存消耗: 77276K, 提交时间: 2018-10-05 14:24:58
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define lb(x) (x&-x)
#define gc() getchar()
typedef long long LL;
const int N=(1<<14)+5,M=5e6;
int pw[16],bit[N],ok[16],sap[N],sdp[N],smp[N],s1[M],s2[M];
LL f[M];
struct Monster
{
int H,A,D,S,ap,dp,mp,hp;
}A[N];
inline int read()
{
int now=0;register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now;
}
LL Combat(Monster mon,LL hp,int atk,int def,int mdf)
{
if(mon.S&8) mon.A=atk, mon.D=def;
if(mon.S&2) def=0;
if(atk<=mon.D) return 0ll;
int dps=atk-mon.D, mon_dps=mon.A<=def?0:mon.A-def;
int tm=(mon.S&4)?2:1;
LL hpbef=hp; hp+=mdf;
if(mon.S&1) hp-=mon_dps*tm;
hp-=1ll*mon_dps*tm*((mon.H+dps-1)/dps-1);
return hp>hpbef?hpbef:hp;
}
int main()
{
pw[0]=1;
for(int i=1; i<=14; ++i) pw[i]=pw[i-1]*3;
for(int i=1; i<=14; ++i) bit[1<<i]=i;
for(int T=read(); T--; )
{
memset(ok,0,sizeof ok), memset(f,0,sizeof f);
int Hp=read(), Atk=read(), Def=read(), Mdf=read();
int n=read();
for(int i=0; i<n; ++i) A[i]=(Monster){read(),read(),read(),read(),read(),read(),read(),read()};
for(int K=read(); K--; ) ok[read()-1]|=1<<(read()-1);
int tot=(1<<n)-1;
for(int s=0; s<=tot; ++s)
{
sap[s]=Atk, sdp[s]=Def, smp[s]=Mdf;
for(int i=0; i<n; ++i) if(s>>i&1) sap[s]+=A[i].ap, sdp[s]+=A[i].dp, smp[s]+=A[i].mp;
}
int lim=pw[n]-1; f[0]=Hp;
for(int s=0; s<lim; ++s)
{
if(!f[s]) continue;//!
int S1=s1[s], S2=s2[s];
for(int i=S1^tot,j; i; i^=lb(i))
{
j=bit[lb(i)];
if((S1&ok[j])!=ok[j]) continue;
f[s+pw[j]]=std::max(f[s+pw[j]],Combat(A[j],f[s],sap[S2],sdp[S2],smp[S2]));
s1[s+pw[j]]=S1|(1<<j), s2[s+pw[j]]=S2;
}
for(int i=S1^S2,j; i; i^=lb(i))
{
j=bit[lb(i)];
f[s+pw[j]]=std::max(f[s+pw[j]],f[s]+A[j].hp);
s1[s+pw[j]]=S1, s2[s+pw[j]]=S2|(1<<j);
}
}
printf("%lld\n",f[lim]?f[lim]:-1ll);
}
return 0;
}