uva 10163 Storage Keepers

题目大意：有N个仓库，M个管理员，M个管理员每个人的工资都不一样，工资与他们的能力值（P）相同。一个管理员可以看管多个（n）仓库，但是仓库的安全值就会变为P / n。现在要是的最小的安全值最大，并且还要求出该状况下的最小花费。

解题思路：两次DP，第一次dp求出最大的最小安全值ans，第二次dp根据第一次dp求出的ans求出最小的花费。

#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         using namespace std; #define N 1005 #define M 105 const int MAX = 0x3f3f3f; int n, m, ans; int dp[N], num[M]; int solve() { //先找出最低安全值的最大值 dp[0] = MAX; for (int i = 0; i < n; i++) { for (int j = m; j >= 0; j--) { for (int k = 1; k <= j && k <= num[i]; k++) { dp[j] = max(dp[j], min(dp[j - k], num[i] / k)); } } } } int find() {//通过上面函数找出的最低安全值的最大值，找出最低酬劳 if(ans == 0) return 0; for (int i = 1; i <= m; i++) dp[i] = MAX; dp[0] = 0; for (int i = 0; i < n; i++) { for (int j = m; j >= 0; j--) { for (int k = min(j, num[i] / ans); k > 0; k--) dp[j] = min(dp[j], dp[j - k] + num[i]); } } } int main() { while (scanf("%d%d", &m, &n) == 2) { memset(dp, 0, sizeof(dp)); if (m == 0 && n == 0) break; for (int i = 0; i < n; i++) scanf("%d", &num[i]); solve(); ans = dp[m]; find(); printf("%d %d\n", ans, dp[m]); } return 0; }