hdu 1158 Employment Planning （动态规划）

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=1158

 

 解题报告：自我感觉这道题目的状态方程不太容易。

刚开始用一维的搞，这么也得不到正确答案，后来想有月份、人数，应该用二维的。 

首先雇主要在第n月花钱最少，一定是在第n-1月花钱也是最少，一定具有最有子结构，可以想到动态规划；

如果第n个月的需要的人数比第n-1个月的多，则需要本月需要(need[n]-need[n-1])*hire+need[n]*salary的钱

如果第n个月的需要的人数比第n-1个月的少，则需要本月需要(need[n-1]-need[n])*fire+need[n]*salary的钱

假设第n-1个月雇佣k个人是最有子结构；

则状态方程：dp[i][j]=dp[i][k]+(need[n]-need[n-1])*hire+need[n]*salary

                  或dp[i][j]=dp[i][k]+(need[n-1]-need[n])*fire+need[n]*salary

 

code：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int INF = 0x7fffffff; 

int hire,salary,fire;
int need[15],dp[15][505];

int main()
{
	int n,mini,maxn,ans;
	while(scanf("%d",&n)&&n)
	{
		maxn=0;
		scanf("%d %d %d",&hire,&salary,&fire);
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&need[i]);
			maxn=max(maxn,need[i]);
		}
		if(maxn==0)
		{
			printf("0\n");
			continue;
		}
		memset(dp,0,sizeof(dp));
		for(int i=need[1];i<=maxn;i++)
		{
			dp[1][i]=(hire+salary)*i;
		}
		int temp; 
		for(int i=2;i<=n;i++)
		{
			for(int j=need[i];j<=maxn;j++)
			{
				mini=INF;
				for(int k=need[i-1];k<=maxn;k++)
				{	
					if(j>=k)
					{
						temp=dp[i-1][k]+(j-k)*hire+j*salary;
					}
					else
					{
						temp=dp[i-1][k]+(k-j)*fire+j*salary;
					}
					mini=min(mini,temp);
				}
				dp[i][j]=mini;
			}
		}
		ans=INF;
		for(int i=need[n];i<=maxn;i++)
		{
			if(ans>dp[n][i])
				ans=dp[n][i];
		}
		printf("%d\n",ans);
	}
	return 0;
}