1158 employment planning.cpp

威士忌的HDU题解.大概有260多题的源码。对于学习非常有好处。

//DP
#include <cstdio>
#include <string>
using namespace std;
const int Max=128;
int m,ch,s,cf;
int minw[13];
int dp[13][Max];

int main()
{
	int i,j,k,t,i2;
	
	while( scanf("%d",&m)!=EOF && m)
	{
		scanf("%d %d %d",&ch,&s,&cf);
		for(i=0;i<m;i++)	
			scanf("%d",&minw[i]);
		memset(dp,0,sizeof(dp));
		dp[0][ minw[0] ]=(ch+s)*minw[0];
		
		for(i=1;i<m;i++)
			for(j=0;j<Max;j++)
				if(dp[i-1][j]!=0)
				{
					if(j>minw[i])
					{
						for(i2=j;i2>=minw[i];i2--)
						{ 
							t=(j-i2)*cf+dp[i-1][j]+i2*s;
							if(dp[i][i2]==0 || dp[i][i2]>t)
								dp[i][i2]=t;
						}
					}
					else if(j<minw[i])
					{
						t=(minw[i]-j)*ch+dp[i-1][j]+minw[i]*s;
						if(dp[i][ minw[i] ]==0 || dp[i][ minw[i] ]>t)
							dp[i][ minw[i] ]=t;
					}
					else 
					{
						t=dp[i-1][j]+j*s;
						if(dp[i][j]==0 || dp[i][j]>t)
							dp[i][j]=t;
					}
				}
			
		for(i=minw[m-1],t=0;i<Max;i++)
		{
			if(dp[m-1][i]==0)
				break;
			if(t==0 || dp[m-1][i]<t)
				t=dp[m-1][i];
		}
		printf("%d\n",t);
	}
	return 0;
}