Storage Keepers

题意：

n个仓库，m个人申请看管仓库，一个人可以看管多个仓库，一个仓库只能被一个人看管，每个人都有一个能力值，他看管的仓库的安全度U是能力值/看管仓库数，安全线L是U中的最小值，有多少能力公司发多少工资，求在保证安全线最高的情况下，公司花费最小。

分析：

状态好想dp[i][j],i个人看管j个仓库能达到的最高安全线,dp[i][j]=max(dp[i][j],min(dp[i-1][k],p[i]/(j-k)));(p是能力值,k是i-1个人看管的仓库数）

下面求最小花费，因为是在安全线最高的前提下，f[i][j]=min(f[i][j],f[i-1][k]+p[i]);要保证安全值大于dp[m][n]即p[i]/(j-k)>=dp[n][m]

#include <map>

#include <set>

#include <list>

#include <cmath>

#include <queue>

#include <stack>

#include <cstdio>

#include <vector>

#include <string>

#include <cctype>

#include <complex>

#include <cassert>

#include <utility>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

using namespace std;

typedef pair<int,int> PII;

typedef long long ll;

#define lson l,m,rt<<1

#define pi acos(-1.0)

#define rson m+1,r,rt<<11

#define All 1,N,1

#define read freopen("in.txt", "r", stdin)

const ll  INFll = 0x3f3f3f3f3f3f3f3fLL;

const int INF= 0x7ffffff;

const int mod =  ;

int dp[][],n,m,p[],f[][];

void solve(){

    for(int i=;i<=n;++i)

        dp[i][]=INF;

    for(int i=;i<=m;++i)

        dp[][i]=;

    for(int i=;i<=n;++i)

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

        dp[i][j]=dp[i-][j];

    for(int k=;k<j;++k){

        dp[i][j]=max(dp[i][j],min(dp[i-][k],p[i]/(j-k)));

    }

    }

    if(dp[n][m]==){printf("0 0\n");return;}

    for(int i=;i<=n;++i)

        f[i][]=;

    for(int i=;i<=m;++i)

        f[][i]=INF;

        for(int i=;i<=n;++i)

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

        f[i][j]=f[i-][j];

    for(int k=;k<j;++k){

        if(p[i]/(j-k)>=dp[n][m])

            f[i][j]=min(f[i][j],f[i-][k]+p[i]);

    }

    }

    printf("%d %d\n",dp[n][m],f[n][m]);

}

int main()

{

    while(~scanf("%d%d",&m,&n)){

        if(n==&&m==)break;

        for(int i=;i<=n;++i)

            scanf("%d",&p[i]);

        solve();

    }

return ;

}

相关文章