Storage Keepers UVA

先二分最小的安全系数，在dp

dp[i][j]表示前i个人管j个仓库的最小值

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;

const int maxn = 1e2+12;

const int maxm = 35;

int n,m,p[maxm],f[maxm][maxn];

int ansmax,ansmin;

bool check(int mid) {
    memset(f,0x3f,sizeof(f));
    for(int i=0;i<=m;i++)f[i][0]=0;
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++) {
            for(int k=j;k>=0;k--) {
                if(j!=k&&p[i]/(j-k)<mid) break;
                f[i][j]=min(f[i][j],f[i-1][k]+(j==k?0:p[i]));
            }
        }
    return f[m][n]<inf?true:false;
}

int main() {
    //freopen("in.txt","r",stdin);
    while(scanf("%d%d",&n,&m)!=EOF&&n&&m) {
        ansmax=0;ansmin=inf;
        int l=0,r=-1;
        for(int i=1;i<=m;i++) scanf("%d",&p[i]),r=max(r,p[i]);
        while(l<=r) {
            int mid=(l+r)>>1;
            if(check(mid)) {ansmax=mid;l=mid+1;ansmin=f[m][n];}
            else r=mid-1;
        }
        if(ansmax) printf("%d %d
",ansmax,ansmin);
        else printf("0 0
");//特判
    }
    return 0;
}