[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
    
     #include
     
      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
      
        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;        }};