一道不错的二分+DP的题目

class Solution {
public:
    int getAns(int n, int k, vector<int> &A, vector<int> &W) {
        if(!n||n==1) return 0;
        int l=0,r=100;

        while(l<r)
        {
            int mid=l+r>>1;
            if(check(n,k,mid,A,W)) r=mid;
            else l=mid+1;
        }

        return l*l;
    }

    int f[105][105];
    //计算使最大差值不超过mid的最小操作次数，是否不超过k
    bool check(int n,int k,int mid,vector<int> &A,vector<int> &W)
    {
        memset(f,0x3f,sizeof f);
        f[0][0]=0;
        for(int i=0;i<=W[0];i++) f[1][i]=abs(i-A[0]);
        for(int i=2;i<=n;i++)
            for(int j=0;j<=W[i-1];j++)
            {
                int x=abs(j-A[i-1]);
                for(int k=max(0,j-mid);k<=min(j+mid,W[i-2]);k++)                
                {
                    f[i][j]=min(f[i][j],f[i-1][k]+x);
                }
            }
        int res=INT_MAX;
        for(int i=0;i<=100;i++) res=min(res,f[n][i]);
        return res<=k;
    }
};