2013
12-03

# Employment Planning

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.

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′.

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

3
4 5 6
10 9 11
0

199

/*

i为月数，l为人数，num[i]为第i月需要多少人，total是最多要多少人。
dp[i][l]=min(dp[i-1][k]+l*s+k>l?(k-l)*f:(l-k)*h)    num[i-1]<=k<=total
ans=min(dp[最后一月][k])         num[最后一月]<=k<=total

2012-05-17
*/

#include"stdio.h"
int min(int a,int b)
{
return a>b?b:a;
}
int main()
{
int n;
int h,s,f;
int num[15];
int i,l,j;
int total;
int dp[12][1011];
int ans;
while(scanf("%d",&n),n)
{
scanf("%d%d%d",&h,&s,&f);
total=0;
for(i=0;i<n;i++)	//i从0开始
{
scanf("%d",&num[i]);
if(total<num[i])	total=num[i];
}
if(total==0)
{
printf("0\n");
continue;
}

for(l=num[0];l<=total;l++)	dp[0][l]=l*(h+s);
for(i=1;i<n;i++)
{
for(l=num[i];l<=total;l++)
{
if(num[i-1]>l)	dp[i][l]=dp[i-1][num[i-1]]+l*s+(num[i-1]-l)*f;
else			dp[i][l]=dp[i-1][num[i-1]]+l*s+(l-num[i-1])*h;
for(j=num[i-1]+1;j<=total;j++)
{
if(j>l)	dp[i][l]=min(dp[i][l],dp[i-1][j]+l*s+(j-l)*f);
else	dp[i][l]=min(dp[i][l],dp[i-1][j]+l*s+(l-j)*h);
}
}
}

ans=111111111;
for(l=num[n-1];l<=total;l++)	ans=min(dp[n-1][l],ans);
printf("%d\n",ans);
}
return 0;
}

1. 是“从05:09到12:09太阳原地旋转了360度”!!!!!!这是用了7小时完成旋转360度，不是视频那样的几秒时间完成旋转360度！说相机旋转的你们什么意思？！

2. #include <cstdio>
#include <algorithm>

struct LWPair{
int l,w;
};

int main() {
//freopen("input.txt","r",stdin);
const int MAXSIZE=5000, MAXVAL=10000;
LWPair sticks[MAXSIZE];
int store[MAXSIZE];
int ncase, nstick, length,width, tmp, time, i,j;
if(scanf("%d",&ncase)!=1) return -1;
while(ncase– && scanf("%d",&nstick)==1) {
for(i=0;i<nstick;++i) scanf("%d%d",&sticks .l,&sticks .w);
std::sort(sticks,sticks+nstick,[](const LWPair &lhs, const LWPair &rhs) { return lhs.l>rhs.l || lhs.l==rhs.l && lhs.w>rhs.w; });
for(time=-1,i=0;i<nstick;++i) {
tmp=sticks .w;
for(j=time;j>=0 && store >=tmp;–j) ; // search from right to left
if(j==time) { store[++time]=tmp; }
else { store[j+1]=tmp; }
}
printf("%dn",time+1);
}
return 0;
}

3. 嗯 分析得很到位，确实用模板编程能让面试官对你的印象更好。在设置辅助栈的时候可以这样：push时，比较要push的elem和辅助栈的栈顶，elem<=min.top()，则min.push(elem).否则只要push（elem）就好。在pop的时候，比较stack.top()与min.top(),if(stack.top()<=min.top()),则{stack.pop();min.pop();}，否则{stack.pop();}.