ACM题目之 招聘计划.doc

招聘计划Time Limit:5000MS Memory Limit:65536KTotal Submit:97 Accepted:8 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。输入数据可以包含若干数据集。每个数据集包含3行。第一行输入这个工程计划的工期(以月为单位)，不超过12个月。第二行包含雇用一个工人的开销，薪水数，和解雇一个工人的开销。第三行包括多个数据，表示每个月需要的最小的工人数。在最后一行输入0表示结束。 Output The output contains one line. The minimal total cost of the project.结果只有一行，为这个项目的最小总开销。Sample Input 3 4 5 610 9 110Sample Output 199Employment Planning 条件DP状态：dpij 前 i 个月，并且第 i 个月留下 j 个人的最小花费 j=numi&j=1&i=numi-1&kj 决策代价 (k-j)*firek=numi&j=1&i=num1&j=numn&j=MaxNum附AC代码：#include#include#define inf 1000000int p,f,h;int tran(int i,int j) if (ij) return (i-j)*f; if (ij) return (j-i)*h; return 0;int small (int a,int b) return ab?a:b;int main() int dp1510000; int i,j,k,n,max,min,res,s,t; int a15; while (scanf(%d,&n)&n) scanf(%d%d%d,&h,&p,&f); max=0; min=inf; for (i=1; imax) max=ai; if (aimin) min=ai; for (i=1; i=n; +i) for (j=min; j=max; +j) dpij=inf; dp0j=0; for (i=1; i=n; +i) for (j=min; j=max; +j) if (i=1) s=t=0; else s=ai-1; t=max; for (k=s; k=t; +k) dpij=small(dpij,