雇佣计划

很久以前做的题，拎出来

Problem Description

一位管理项目的经理想要确定每个月需要的工人，他当然知道每月所需的最少工人数。当他雇佣或解雇一个工人时，会有一些额外支出。一旦一个工人被雇佣，即使他不工作，他也将得到工资。这位经理知道雇佣一个工人的费用，解雇一个工人的费用和一个工人的工资。

现他在考虑一个问题：为了把项目的费用控制在最低，他将每月雇佣多少个工人。

Input Format

共三行。

第一行为月数n(不超过12)。
第二行含雇佣一个工人的费用，一个工人的工资和解雇一个工人的费用（<=100）。
第三行含n个数，分别表示每月需要的工人数（<=1000）。每个数据之间有一个空格隔开。

Output Format

仅一行，表示项目的最小总费用。

Algorithm Design

贪心算法

Problem Analysis

这道题因素过于复杂，打爆搜不可能看出规律。两个可能的突破口：1.月数n非常小。2.工人的支出都是统一的。顺向思维，第一个工作月当然要雇佣需要的工人 数。接下来面临三种情况：1.工人缺少2.工人恰好3.工人冗余。前两种处理方式十分简单，缺就雇，不缺就照常。可见这题全部的难点都在一个问题上：怎么 处理工人冗余的情况。解不解雇？解雇几个人？仔细思考一下这个问题。

不难发现，这题其实还是存在最优解子结构和无后效性的，把工作月需要的工人想象成山高，而我们要处理的问题是峰谷之间的问题，这个时候处理几个工人并不重要，1，2,3，一直到峰差都是一样的处理，只是峰距不一样罢了

1.解雇，需要两（一）次费用：解雇费和雇佣费（如果之后还有山峰的话）

2.留用，既然留用，就不存在留用一段时间再解雇的情况，那是完全的亏损，而留用至少会让他待到下一个山峰，那时候又是另一个子问题不管，所以需要峰距*月薪

那么问题的重点已经呼之欲出：计算峰距

利用突破口1，穷举都是完全可以的，所以这个问题已经基本上被解决了。

一遍就过掉了~

Source Code

#include <bits/stdc++.h>

using namespace std;

int n,hire,cut,paid,w[13],had,cost;
//hire雇佣费，paid月薪，cut解雇费，had当前工人，cost总花费
int main()
{
    freopen("test.in","r",stdin);
    freopen("test.out","w",stdout);
    cin>>n>>hire>>paid>>cut;
    for(int i=1;i<=n;i++)
        cin>>w[i];
    had=w[1],cost=(hire+paid)*w[1];//将第一月的工人全部招入
    for(int i=2;i<=n;i++)    
    {
        cost+=paid*w[i];//将起码要工作的工人工资发下
        if(w[i]>=had)
        {
            cost+=hire*(w[i]-had);
            had=w[i];
            continue;
        }//如果工人数不够则补充
        int gap=had-w[i];//计算多余的工人数
        for(int j=1;j<=gap;j++)
        {
            int sub=n+1,cost1=0,cost2=0;
            for(int k=i+1;k<=n;k++)
                if(w[k]>=w[i]+j)
                {
                    sub=k;
                    cost1=hire;//如果存在下一个山峰还要再雇佣一次
                    break;
                }//针对多出的工人数找到第一个有用处的山峰
            cost1+=cut,cost2=paid*(sub-i);
//解雇方案加上解雇费，留用方案加上工资
            if(cost1>=cost2)cost+=paid;
            else cost+=cut,had--;
//选择最适当的方案
        }
    }
    cout<<cost<<endl;
    return 0;
}