题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1158

Employment Planning

3 
4 5 6
10 9 11
0

199

        （1）：先明确dp[][]的含义，dp[i][j]表示第i个月，工作人数为j时的最优解；用a[]数组存储每个月的最少的工作人数，用maxn存储n个月最大的工作人数，那么最终的最优解就得从dp[n][a[n]].....dp[n][maxn]找出一个最小值；

         （2）：明确状态转移方程：dp[i][j]=min(dp[i-1][k]+cost[k]);  (a[i-1]<=k<=maxn,cost[k]表示人数从k个人变为j个人的花费);

          附上AC代码：

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <string>
#include <cstdio>
#include <cmath>
const int INF=99999999;
using namespace std;
int a[15];
int dp[15][1000];

int main()
{
        int n;
        int hire_cost,work_cost,fire_cost;
        while(cin>>n&&n)
        {
            cin>>hire_cost>>work_cost>>fire_cost;
            int maxn=0;
            for(int i=1;i<=n;i++)
            {
               cin>>a[i];
               if(a[i]>maxn)maxn=a[i];
            }

            for(int i=a[1];i<=maxn;i++)dp[1][i]=(hire_cost+work_cost)*i;

            for(int i=2;i<=n;i++)
             for(int j=a[i];j<=maxn;j++)
                {
                  dp[i][j]=INF;
                  for(int k=a[i-1];k<=maxn;k++)
                  {
                     if(k<j)dp[i][j]=min(dp[i][j],dp[i-1][k]+(j-k)*hire_cost+j*work_cost);
                     else   dp[i][j]=min(dp[i][j],dp[i-1][k]+(k-j)*fire_cost+j*work_cost);
                  }
                }
           int m=INF;
           for(int i=a[n];i<=maxn;i++)
           {
              if(dp[n][i]<m)m=dp[n][i];
           }
          cout<<m<<endl;
        }
  return 0;
}

hdu 1158（dp）

原文：http://blog.csdn.net/liusuangeng/article/details/38817003