uva 10163 Storage Keepers （DP）

uva 10163 Storage Keepers （DP）

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;  
}