题意：
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 = 1000000007; int dp[35][110],n,m,p[35],f[35][110]; void solve(){ for(int i=0;i<=n;++i) dp[i][0]=INF; for(int i=1;i<=m;++i) dp[0][i]=0; for(int i=1;i<=n;++i) for(int j=1;j<=m;++j){ dp[i][j]=dp[i-1][j]; for(int k=0;k<j;++k){ dp[i][j]=max(dp[i][j],min(dp[i-1][k],p[i]/(j-k))); } } if(dp[n][m]==0){printf("0 0\n");return;} for(int i=0;i<=n;++i) f[i][0]=0; for(int i=1;i<=m;++i) f[0][i]=INF; for(int i=1;i<=n;++i) for(int j=1;j<=m;++j){ f[i][j]=f[i-1][j]; for(int k=0;k<j;++k){ if(p[i]/(j-k)>=dp[n][m]) f[i][j]=min(f[i][j],f[i-1][k]+p[i]); } } printf("%d %d\n",dp[n][m],f[n][m]); } int main() { while(~scanf("%d%d",&m,&n)){ if(n==0&&m==0)break; for(int i=1;i<=n;++i) scanf("%d",&p[i]); solve(); } return 0; }
原文：http://www.cnblogs.com/zsf123/p/4890258.html