ZJU/ZOJ 1454 Employment Planning 解题报告

题目大意是有一项工程每个月需要雇佣一定的工人，给出雇佣一个工人的费用、一个工人一个月的工资、解雇一个工人的费用以及每个月需要的工人人数，问完成这项工程最少需要花费多少钱。

只想到了时间复杂度是O(mn^2)的DP。m是月份数，n=单月最大所需工人数-该月所需工人数。状态转移方程是f[i,j]=min(f[i,j],f[i-1,k]+(j-k)*c1+j*c2)(k<j);min(f[i,j],f[i-1,k]+(k-j)*c3+j*c2)(k>=j)。f[i,j]表示第i个月雇佣j个人所需的最小费用，c1是雇佣费用，c2是工资，c3是解雇费用。

3021173 2008-08-04 16:05:27 Accepted 1454 FPC 00:00.27 416K IwfWcf@LZOI