Employment Planning-白红宇

Employment Planning

阅读量：192 次

发布时间：2019-02-28

本文共 1553 字，大约阅读时间需要 5 分钟。

为了解决这个问题，我们需要确定在每个月雇佣或解雇工人时的最小总成本。这个问题可以通过动态规划来解决，具体步骤如下：

方法思路

状态定义：使用二维数组 f[i][j] 表示前 i 个月，第 i 个月恰好有 j 名工人时的最小总成本。

状态转移：

如果雇佣人数增加，计算雇佣新员工的成本。

如果解雇人数减少，计算解雇员工的成本。

初始条件：第一个月必须雇佣至少 min_worker 名工人。

优化：预处理每个月的最小员工需求，限制 j 的范围，减少状态空间。

解决代码

#include 
   
    #include 
    
     #include 
     
      #include 
      #include 
       
        #include 
        
         #include 
         
          using namespace std;int main() { int n, hire, salary, fire; while (cin >> n && n != 0) { int min_worker[] = {0}, maxn = 0; for (int i = 1; i <= n; ++i) { cin >> min_worker[i]; if (min_worker[i] > maxn) maxn = min_worker[i]; } cin >> hire >> salary >> fire; int size = maxn + 1; int f[n+1][size]; for (int i = 0; i <= n; ++i) { for (int j = 0; j <= size; ++j) { f[i][j] = 1e9; } } for (int j = min_worker[1]; j <= maxn; ++j) { f[1][j] = (hire + salary) * j; } for (int i = 2; i <= n; ++i) { for (int j = min_worker[i]; j <= maxn; ++j) { for (int k = min_worker[i-1]; k <= maxn; ++k) { if (j > k) { if (f[i][j] > f[i-1][k] + (j - k) * hire + j * salary) { f[i][j] = f[i-1][k] + (j - k) * hire + j * salary; } } else { if (f[i][j] > f[i-1][k] + (k - j) * fire + j * salary) { f[i][j] = f[i-1][k] + (k - j) * fire + j * salary; } } } } } int ans = 1e9; for (int j = min_worker[n]; j <= maxn; ++j) { if (f[n][j] < ans) { ans = f[n][j]; } } cout << ans << endl; }}