HDU1158：Employment Planning（线性dp)

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

这题又是看了题解，题意是一项工作需要n个月完成，雇佣一个人需要m1的钱，一个人的月工资为sa,辞退一个人需要花费m2的钱，然后给出n的数字，

代表每月需要的最少员工，问如何进行人员调整使最终花费的钱最少。

我已开始就推错了状态转移方程，因为给出的是最少的员工，所以要从当前最少员工~最多员工枚举。

还有每次需要比较num[i-1]与num[i]的大小，具体实现请看代码。

#include <iostream>

#include <stdio.h>

#include <string.h>

#include <algorithm>

#define inf 0x3f3f3f3f

using namespace std;

int n,dp[13][110];

int m1,sa,m2,num[13],maxx;

int main()

{

    while(scanf("%d",&n)!=EOF&&n!=0)

    {

        scanf("%d%d%d",&m1,&sa,&m2);

        maxx=-inf;

        for(int i=1; i<=n; i++)

        {

            scanf("%d",&num[i]);

            maxx=max(maxx,num[i]);

        }

        for(int i=0;i<=n;i++)

        {

            for(int j=0;j<=maxx;j++)

                dp[i][j]=inf;

        }

        for(int i=1;i<=maxx;i++)

        {

            dp[1][i]=i*m1+i*sa;

            //printf("dp[1][%d]==%d\n",i,dp[1][i]);

        }

        for(int i=2;i<=n;i++)

        {

            for(int j=num[i];j<=maxx;j++)

            {

                for(int k=num[i-1];k<=maxx;k++)

                {

                    if(k>=j)

                    dp[i][j]=min(dp[i][j],dp[i-1][k]+(k-j)*m2+j*sa);

                    else

                    dp[i][j]=min(dp[i][j],dp[i-1][k]+(j-k)*m1+j*sa);

                }

                 //printf("dp[%d][%d]==%d\n",i,j,dp[i][j]);

            }

        }

       int minx=inf;

       for(int i=num[n];i<=maxx;i++)

        minx=min(minx,dp[n][i]);

       printf("%d\n",minx);

    }

    return 0;

}

巴特西

HDU1158：Employment Planning（线性dp)

最新文章

热门文章