hdu 1158-Employment Planning，nnn

解题思路就不多说，动态规划。

值得提及的是题目没有给出数据范围，水过的都默认工人数目不超过1000。

我给出了n*n*n的算法，针对工人数目任意的情况。

首先，可以判断的是，每次决策之后的工人数量，肯定和从当前月开始的之后某个月的工人数量相同

如要hire，则当hire足够；如要fire，则当fire到底；

如此就可以应离散化的方法了，n*n*n。转移为o(n)

#include<algorithm>  
#include<iostream>  
#include<cmath>  
#include<stdio.h>  
#include<stdlib.h>  
#include<cstring>  
using namespace std;  
  
#define N 15  
int dp[N][N];  
int hire,sala,fire;  
int num[N];  
int disf[N];  
int pos[N];  
int main()  
{  
    int i,j,k,n,tmp;  
    while(~scanf("%d",&n) && n)  
    {  
        scanf("%d%d%d",&hire,&sala,&fire);  
        for(i=0;i<n;disf[i]=num[i],i++)scanf("%d",&num[i]);  
        sort(disf,disf+n);  
        for(i=0;i<n;pos[i]=j,i++)for(j=0;j<n && num[i]!=disf[j];j++);  
        memset(dp,-1,sizeof(dp));  
        dp[0][pos[0]]=(hire+sala)*num[0];  
          
        for(i=1;i<n;i++)  
        for(k=pos[i];k<n;k++){  
          
        for(j=pos[i-1];j<n;j++)  
        if(dp[i-1][j]!=-1){  
            if(j<k)tmp=dp[i-1][j]+(disf[k]-disf[j])*hire+disf[k]*sala;  
            else tmp=dp[i-1][j]+(disf[j]-disf[k])*fire+disf[k]*sala;  
  
            if(dp[i][k]==-1)dp[i][k]=tmp;  
            else dp[i][k]=min(dp[i][k],tmp);  
        }  
          
        }  
    /* 
    for(i=0;i<n;i++) 
    { 
    for(j=0;j<n;j++) 
    printf("%d ",dp[i][j]); 
    printf("\n"); 
    } 
*/    
    int minp=dp[n-1][pos[n-1]];  
        for(j=pos[n-1]+1;j<n;j++)  
            minp=min(minp,dp[n-1][j]);  
        printf("%d\n",minp);  
        }  
    return 0;  
}  
/* 
3 
4 5 6 
10 9 11 

*/

补充：软件开发 , C++ ,

hdu 1158-Employment Planning，n*n*n

hdu 1158-Employment Planning，nnn