hdu 1158 Employment Planning (DP)

클릭하여 링크 열기
제목:
1. n대표가 일해야 할 총 월수를 하나 줄게.
2, 당신 노동자 의 고용 임금 hire, 월 임금 salary, 해고 임금 fire
3, 매달 필요한 일꾼 수
최소 비용을 요구하다
dp[i][j]는 i개월 동안 j명의 노동자를 사용하는 최소 비용을 대표한다

#include <stdio.h>
int man[15];
int dp[15];
#define INF 0x7FFFFFFF
int main()
{
	int month,i;
	int hire,salary,fire,temp;
	while(scanf("%d",&month)==1&&month)
	{
		scanf("%d%d%d",&hire,&salary,&fire);
		for(i=1;i<=month;i++)
			scanf("%d",&man[i]);
		man[0] = 0;
		for(int i=1;i<=month;i++)
		{
			dp[i] = INF;
			temp = 0;
			for(int j=i-1;j>=0;j--)
			{
				if(temp > man[i]) break;
				if(man[j]<temp) continue;
				temp = man[j];
				int newcost;
				if(temp >= man[i])
				{
					newcost = dp[j] + fire * (temp-man[i]) + salary * (i-j) * man[i];
				}
				else
				{
					newcost = dp[j] + hire * (man[i]-temp) + salary * (i-j-1) * temp + salary * man[i];
				}
				if(dp[i] > newcost)
					dp[i] = newcost;
			}
			//printf("dp[%d] = %d
",i,dp[i]);
		}
		dp[month+1] = INF;
		temp = 0;
		for(int j=month;j>0;j--)
		{
			if(man[j]<temp) continue;
			temp = man[j];
			int newcost = dp[j] + salary * (month-j) * temp;
			if(dp[month+1] > newcost)
				dp[month+1] = newcost;
		}
		printf("%d
",dp[month+1]);
	}
	return 0;
}