SRM 658 DIV1 650 二分答案 动态规划

题目链接：暂无

题目大意：
有 n 个数，每次操作可以选择 ≤3 个数，将其中一个数减 9 ，一个数减 3 ，一个数减 1 ，不能减同一个数，询问最少多少次操作可以令所有数 ≤0

题解：
二分枚举答案 lim ，那么就可以将操作拆分来看，有 lim 次减 9 操作， lim 次减 3 操作， lim 次减 1 操作，但是对于某个数的总操作次数不能大于 lim （此时这个数一定在某次操作中被同时被减）
用 f[i][A][B] 表示已经将 i−1 个数减为非正数，还能用 A 次减 9 操作， B 次减 3 操作时剩余的最大的减 1 操作的次数
那么 f[i][A][B]=max{f[i−1][A+a][B+b]−c} （将第 i 个数减为非正用了 a 次减 9 操作， b 次减 3 操作， c 次减 1 操作）
如果 ∃A,B≥0 使得 f[n][A][B]≥0 那么 lim 可行

代码：

#include <bits/stdc++.h>
using namespace std;
class Mutalisk
{
    private:
    int n;
    int f[21][94][94];
        bool Judge(const vector<int>&x,int lim)
        {
            memset(f,-1,sizeof f);
            f[0][lim][lim]=lim;
            for(int i=1;i<=n;i++)
                for(int A=0;A<=lim;A++)
                for(int B=0;B<=lim;B++)
                    if(dp[i-1][A][B]>=0)
                        for(int a=0;a<=A;a++)
                        for(int b=0;b<=B;b++)
                        {
                            int c=max(0,x[i-1]-a*9-b*3);
                            if(a+b+c>lim) continue;
                            if(c>f[i-1][A][B]) continue;
                            f[i][A-a][B-b]=max(f[i][A-a][B-b],f[i-1][A][B]-c);
                        }
            for(int A=0;A<=lim;A++)
            for(int B=0;B<=lim;B++)
                if(f[n][A][B]>=0)
                    return 1;
            return 0;
        }
    public:
        int minimalAttacks(vector<int>x)
        {
            n=x.size();
            int l=1,r=93,re,mid;
            while(l<=r)
            {
                mid=(l+r)>>1;
                if(Judge(x,mid))
                {
                    re=mid;
                    r=mid-1;
                }
                else l=mid+1;
            }
            return re;
        }
};