程序代码：

#include <stdio.h>
#include <stdlib.h>
#define max_workers 100
#define MIN(a,b) (a>b?b:a)

int process_step(int *step,int **trace,const int *min_workers,const int *spend,int month)
{
    int i,j,k,step_min,tmp,trace_worker;
    for (i=min_workers[month];i<=max_workers ;i++ )
    {
        step_min = step[max_workers] + max_workers*spend[1] + (max_workers-i)*spend[2];
        trace_worker = max_workers;
        for (j=min_workers[month-1];j<=max_workers ;j++ )
        {
            if (i>j)
                tmp = step[j] + j*spend[1] + (i-j)*spend[0];
            else
                tmp = step[j] + j*spend[1] + (j-i)*spend[2];
            if (step_min>tmp)
            {
                step_min = tmp;
                trace_worker = j;
            }
        }
        step[i] = step_min;
        for (k=0;k<month ;k++ )
        {
            trace[i][k] = trace[trace_worker][k];
        }
        trace[i][month] = i;
    }
}

int main()
{
    // inputs.
    int month;
    int spend[3];

    scanf("%d\n",&month);

    if (month>12 || month<=0)
    {
        printf("Error in input month: month must be >0 and <=12!");
        exit(1);
    }

    scanf("%d %d %d\n",spend+0,spend+1,spend+2);

    int min_workers[month];
    int step[max_workers+1];
    int min_cost;
    int **trace;
    int i=0,kk;

    while(1)
    {
        scanf("%d",&kk);
        if (kk==0) break;
        min_workers[i++]=kk;
    }
    if (i!=month)
    {
        printf("Error in input min workers in each month!");
        exit(1);
    }
   
    // save dynamic programm traces
    trace = (int **)malloc((max_workers+1)*sizeof(int *));
    for (i=0;i<=max_workers ;i++ )
        trace[i] = (int *)malloc(month*sizeof(int));


    // initail worker
    for (i=min_workers[0];i<=max_workers ;i++ )
    {
        step[i] = spend[0]*i;
        trace[i][0]=i;
    }

    //dp process
    for (i=1;i<month ;i++ )
        process_step(step,trace,min_workers,spend,i);

    //make last step
    min_cost = step[min_workers[month-1]]+min_workers[month-1]*spend[1];
    for (i=min_workers[month-1] ;i<=max_workers;i++ )
    {
        if (min_cost>=step[i]+i*spend[1])
        {
            kk = i;
        }
        min_cost = MIN(min_cost,step[i]+i*spend[1]);
    }

    //print output
    printf("The min cost is %d\n",min_cost);
    printf("Each month workers is:  ");
    for (i=0;i<month ;i++ )
    {
        printf("%d\t",trace[kk][i]);
    }
}
    

程序代码：

#include <stdio.h>
#include <stdio.h>
#include <string.h>
#include <limits.h>
#define min(x,y) (x)>(y)?(y):(x)
#define maxn 300
#define inf INT_MAX
int dp[14][maxn];
int main()
{
    int n,h,s,f,max,min,q,tmp;
    int a[14],k,i,j,mmax;
    while(scanf("%d",&n),n)
    {
        //max=-;
        min=inf;
        mmax=inf;
        for(i=0;i<13;i++)
        for(j=0;j<300;j++)
        dp[i][j]=inf;
        scanf("%d%d%d",&h,&s,&f);
        for(i=0;i<n;i++)
        {scanf("%d",&a[i]);}
        max=a[0];
        dp[0][max]=a[0]*h+a[0]*s;
        min=max;
        
        
        //printf("--%d\n",dp[0][max]);
        for(i=1;i<n;i++)
        {
            for(int p=max;p>=min;p--)
            {
                if(p>=a[i])
                {
                    for(q=p;q>=a[i];q--)
                    {
                        dp[i][q]=min(dp[i][q],(dp[i-1][p]+(p-q)*f+q*s));
            //    printf("%d\n",dp[i][q]);
                    }
                }
                else
                {
                    for(q=p;q<=max;q++)
                    {
                        if(q>=a[i])
                dp[i][q]=min(dp[i][q],(dp[i-1][p]+(q-p)*h+q*s));
            else
            {
                dp[i][a[i]]=min(dp[i][a[i]],(dp[i-1][p]+(a[i]-p)*h+a[i]*s));        
            }
                    }
                    //dp[i][a[i]]=min(dp[i][a[i]],(dp[i-1][p]+(a[i]-p)*h+q*s));
                    //dp[i][a[i]]=min(dp[i][a[i]],(dp[i-1][p]+(a[i]-p)*h+a[i]*s));
                }
        }
            if(max<a[i])max=a[i];
            if(a[i]<min)min=a[i];
        }
    //for(i=0;i<n;i++)
        for(j=a[n-1];j<=max;j++)
           {mmax=min(mmax,dp[n-1][j]);}
        printf("%d\n",mmax);
    }
    return 0;
}