求大牛们帮我看看这题应该怎么来解啊？解这样类型的题目思路应该怎么来考虑啊？？？


Problem Description：
A project manager wants to determine the number of the workers needed in every month. He does know the minimal number of the workers needed in each month. When he hires or fires a worker, there will be some extra cost. Once a worker is hired, he will get the salary even if he is not working. The manager knows the costs of hiring a worker, firing a worker, and the salary of a worker. Then the manager will confront such a problem: how many workers he will hire or fire each month in order to keep the lowest total cost of the project.

Input：
The input may contain several data sets. Each data set contains three lines. First line contains the months of the project planed to use which is no more than 12. The second line contains the cost of hiring a worker, the amount of the salary, the cost of firing a worker. The third line contains several numbers, which represent the minimal number of the workers needed each month. The input is terminated by line containing a single '0'.

Output：
The output contains one line. The minimal total cost of the project.

Sample Input：
3
4 5 6
10 9 11
0
Sample Output
199

看不懂英文，谁换一个中文上来呀

LZ自己看吧，思路自己想想。
自己观察一下，也测试下我写的对不对。

#include<stdio.h>
int main()
{
    int month,hire,fire,salary;
    int a[12],total=0,numworkers=0;
    puts("how much money will be cost when hiring or firing a worker and"
    "the salary for each month");
    scanf("%d%d%d",&hire,&salary,&fire);
    puts("input month");
    scanf("%d",&month);
    puts("input the mininl number of wokers needed each month");
    for(int i=0;i<month;i++)
    {
        scanf("%d",&a[i]);
    }
    for(int i=0;i<month;i++)
    {
        if(numworkers<=a[i])
        {
            total+=hire*(a[i]-numworkers)+salary*a[i];
            numworkers=a[i];
        }
        else
        {
            if(salary<fire)
            {
                total+=salary*numworkers;
            }
            else
            {
                total+=fire*(numworkers-a[i])+salary*a[i];
                numworkers=a[i];
            }
        }
    }
    printf("total=%d\n",total);
    return 0;
}
        

收到的鲜花

• Devil_W 于 2010-04-10 19:52 送鲜花  -2朵   附言：你懂什么是OJ不？
• pgy 于 2010-04-12 01:37 送鲜花  2朵   附言：不经打击总天真
• pgy 于 2010-04-12 01:41 送鲜花  1朵   附言：未经清平难做人

首先要确定有几个月 如果是一个月 也就没意思啦
 根据每个月的最少人数的不同 如果每个月最少人数是相同的 就不用编了
   所以  就导出  雇佣 和 解雇 之间的关系
        员工 每个月都要发工资  解雇 就要付一定的违约金  在两者之间权衡得失
开始

收到的鲜花

• jcslt 于 2010-04-26 14:29 送鲜花  6朵   附言：学习下。。。

这叫白说 几个月的人数都要连续考虑的

错了

TO:Devil_W  
本人才疏学浅，不懂得什么。也从不玩ACM。不懂的OJ，如果Devil_W 大侠知道可以说说，给大家讲讲，不过我没兴趣，我承认本人很菜的，这题我做错了，那还是请Devil_W 大侠来指教下，我很乐意学习，不知道Devil_W大侠在论坛逛着是给人挑错的
(如果有错当然愿意他人指点）还是教人学习的，还是表现你自己的（不针对这个帖子），有人虚心请教，有人客气回答，
同是为了学习。敢问大侠您是为什么？
PS：别说你没有过很菜的过去。

收到的鲜花

• pgy 于 2010-04-12 01:39 送鲜花  -1朵   附言：版主大人淡定

感觉有点。。。。。

假设输入文件中的数字如下
n
a b c
a0,a1,a2....an-1
定义一个函数 int zhengshu(int n) //如果n是正数，返回n。如果n是非正数字  返回0
设各个月的员工数b[0],b[1]...b[n-1]
设各个月的消费c[0],c[1]...c[n-1]
则有
c[0]=b[0]*a+b[0]*b;
c[1]=zhengshu(b[1]-b[0])*a /*固人所需要的费用*/ +zhengshu(b[0]-b[1])*c /*解雇所需要的费用*/ + b[1]*b /*工资所需要的费用*/
.....
c[n-1]=zhengshu(b[n-1]-b[n-2])*a /*固人所需要的费用*/ +zhengshu(b[n-2]-b[n-1])*c /*解雇所需要的费用*/ + b[n-1]*b /*工资所需要的费用*/

设总费用计为s，则s=c[0]+c[1]+...+c[n-1]
设 max=max{a0,a1...an-1}
则s中的约束条件是
a0<=b[0]<=max
a1<=b[1]<=max
...
an-1<=b[n-1]<=max

综上用for循环遍历b[0]到b[n-1]的各种组合情况，可以求出s的最小值！

#include<iostream>
using namespace std;
class cost{
public:
    cost(int count=0){
        count_month=count;
        buf=new int[count_month];
    }
    cost(int count,int hire,int sal,int fire)
        {
            count_month=count;
            cost_hire=hire;
            salary=sal;
            cost_fire=fire;
            buf=new int[count_month];
            for(int i=0;i<count_month;i++)
            {
                cin>>buf[i];
            }
        }
    int sum_cost()
        {
            int sum=0,cur_hires=0;
            for(int i=0;i<count_month;i++)
            {
                if(cur_hires<=buf[i])
                {
                    sum += cost_hire*(buf[i]-cur_hires)+salary*buf[i];
                    cur_hires=buf[i];
                }
                else
                {
                    if(salary<cost_fire)
                    {
                        sum += salary*cur_hires;
                    }
                    else
                    {
                        sum += cost_fire*(cur_hires-buf[i])+salary*buf[i];
                        cur_hires=buf[i];
                    }
                }
            }
            return sum;
        }
    ~cost(){
        delete[] buf;
    }
    
private:
    int *buf;
    int count_month;
    int cost_hire;
    int salary;
    int cost_fire;
};
int main()
{
    int months;
    while(cin>>months)
    {
        if(months==0)
            break;
        int hire,sal,fire;
        cin>>hire>>sal>>fire;
        cost c(months,hire,sal,fire);
        cout<<c.sum_cost()<<endl;
    }
    return 0;
}

收到的鲜花

• pgy 于 2010-04-12 01:43 送鲜花  10朵   附言：好玩，哈~
• jcslt 于 2010-04-26 14:30 送鲜花  6朵   附言：呵呵，学习。。。