ovo的憨憨题解

题目解释

1.当好人卡伤害总和恰好等于hp时才算有解

2.每张好人卡可以使用多次

3.hp<=10000

做法详解

//首先别用递归，会TLE

直接上代码吧ovo

for (int i = 0; i <= hp; i++)

{

if (a[i] == true)

{

for (int j = 1; j <= 4; j++)

{

if(i+d[j]<=hp)

a[i + d[j]] = true;

}

}

}

a[i]表示好人卡伤害总和是否能到i

d[j]表示第j位女生的好人卡伤害

如果a[i]=true，则可以在i的基础上再加上每张卡的伤害，表示总伤害可以达到i+d[j]

所以一遍下来后判断一下a[hp]是true还是false就行

时间复杂度理论O(n)，不会超时ovo

精妙的BFS做法！

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%