首页 > ACM题库 > HDU-杭电 > HDU 1158 Employment Planning-动态规划-[解题报告] C++
2013
12-03

HDU 1158 Employment Planning-动态规划-[解题报告] C++

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. #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;
    }

  2. 嗯 分析得很到位,确实用模板编程能让面试官对你的印象更好。在设置辅助栈的时候可以这样: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();}.

  3. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  4. 一开始就规定不相邻节点颜色相同,可能得不到最优解。我想个类似的算法,也不确定是否总能得到最优解:先着一个点,随机挑一个相邻点,着第二色,继续随机选一个点,但必须至少有一个边和已着点相邻,着上不同色,当然尽量不增加新色,直到完成。我还找不到反例验证他的错误。。希望LZ也帮想想, 有想法欢迎来邮件。谢谢

  5. 我没看懂题目
    2
    5 6 -1 5 4 -7
    7 0 6 -1 1 -6 7 -5
    我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
    第二个是7 0 6 -1 1 -6 7输出是14 7 7
    不知道题目例子是怎么得出来的