HDU - 1158
程序员文章站
2022-07-16 10:21:36
...
推荐博客:
https://blog.csdn.net/hhq420684/article/details/37651489
https://blog.csdn.net/keyboarderqq/article/details/52579170
这里有几个注意点:
(1)
dp的初始化。因为没有前面的状态(它本身是第一个状态),所以无论有多少人,都是这一轮雇来的,所以是cost[1]*i。
(2)
因为下面要取min,所以这一步应该变为INF,但是绝对不能用memset(do,INF,sizeof(dp))这样。因为这样答案全部是INF。
(3)
这里不是将dp[1]---dp[N]的全部任务的每一个最小值相加求和为答案,因为
dp[i]已经把dp[i-1]的状态累加进去了(理解为前缀和吧)
代码:
//J
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define MAXN 15
#define MAXN2 10010
#define INF 0x7f7f7f7f
int num[MAXN];//为每个月最少需要的人数
int cost[4];//分别为雇人,工资和炒人
int dp[MAXN][MAXN2];//dp[i][j]表示第i个项目,有j个人的总经费
int main()
{
int i,j,k;
int N;
int maxn;
int ans;
while(scanf("%d",&N)&&N)
{
memset(cost,0,sizeof(cost));
scanf("%d%d%d",&cost[1],&cost[2],&cost[3]);
memset(num,0,sizeof(num));
maxn=0;
for(i=1;i<=N;i++)
{
scanf("%d",&num[i]);
maxn=max(maxn,num[i]);
}
for(i=0;i<=maxn;i++)
dp[0][i]=cost[2]*i+cost[1]*i;
for(i=1;i<=N;i++)
{
for(j=num[i];j<=maxn;j++)
{
dp[i][j]=INF;
for(k=num[i-1];k<=maxn;k++)
{
if(k<j)
dp[i][j]=min(dp[i][j],j*cost[2]+dp[i-1][k]+(j-k)*cost[1]);
else if(k>j)
dp[i][j]=min(dp[i][j],j*cost[2]+dp[i-1][k]+(k-j)*cost[3]);
else
dp[i][j]=min(dp[i][j],j*cost[2]+dp[i-1][k]);
}
}
}
ans=dp[N][num[N]];
for(i=num[N]+1;i<=maxn;i++)
ans=min(ans,dp[N][i]);
printf("%d\n",ans);
}
return 0;
}
上一篇: 【面试题】丑数(动态规划)
下一篇: 91. 解码方法
推荐阅读
-
HDU6315 Naive Operations(线段树 复杂度分析)
-
【题解】hdu1506 Largest Rectangle in a Histogram
-
oracle https://localhost:1158/em 无法打开
-
C - Monkey and Banana HDU 1069( 动态规划+叠放长方体)
-
HDU 1052(田忌赛马 贪心)
-
hdu-1338 game predictions(贪心题)
-
致初学者(四):HDU 2044~2050 递推专项习题解
-
C语言BFS--Find a way(Hdu 2612)
-
『ACM C++』HDU杭电OJ | 1425 - sort (排序函数的特殊应用)
-
【hdu5527】【2015ACM/ICPC亚洲区长春站 】Too Rich