[TC13761]Mutalisk

题目大意：

有\(n(n\le20)\)个坏人，第\(i\)个坏人的血量为\(A_i(A_i\le60)\)。你可以每次攻击\(3\)个坏人，并分别造成\(9\)点、\(3\)点、\(1\)点伤害。问最少需要多少次攻击使得所有坏人血量都\(\le0\)。

思路：

二分+DP。

\(f_{i,j,k}\)表示前\(i\)个坏人，还有\(j\)次扣\(9\)点血的机会、\(k\)次扣\(3\)点血的机会，最多还能有几次扣\(1\)点血的机会。

源代码：

#include<vector>

#include<cstring>

class Mutalisk {

	private:

		static constexpr int N=21,M=101;

		int n,a[N],f[N][M][M];

		void upd(int &a,const int &b) {

			a=std::max(a,b);

		}

		bool check(const int &m) {

			memset(f,-1,sizeof f);

			f[0][m][m]=m;

			for(register int i=1;i<=n;i++) {

				for(register int j=0;(j-1)*9<=a[i]&&j<=m;j++) {

					for(register int k=0;(j-1)*9+(k-1)*3<=a[i]&&j+k<=m;k++) {

						const int l=std::max(a[i]-j*9-k*3,0);

						if(j+k+l>m) continue;

						for(register int a=j;a<=m;a++) {

							for(register int b=k;b<=m;b++) {

								upd(f[i][a-j][b-k],f[i-1][a][b]-l);

							}

						}

					}

				}

			}

			for(register int i=0;i<=m;i++) {

				for(register int j=0;j<=m;j++) {

					if(f[n][i][j]!=-1) return true;

				}

			}

			return false;

		}

	public:

		int minimalAttacks(std::vector<int> x) {

			n=x.size();

			for(register int i=1;i<=n;i++) {

				a[i]=x[i-1];

			}

			int l=1,r=100;

			while(l<=r) {

				const int mid=(l+r)>>1;

				if(check(mid)) {

					r=mid-1;

				} else {

					l=mid+1;

				}

			}

			return r+1;

		}

};