题目链接:
http://acm.hdu.edu.cn/showproblem.php?pid=1158
解题报告:自我感觉这道题目的状态方程不太容易。
刚开始用一维的搞,这么也得不到正确答案,后来想有月份、人数,应该用二维的。
首先雇主要在第n月花钱最少,一定是在第n-1月花钱也是最少,一定具有最有子结构,可以想到动态规划;
如果第n个月的需要的人数比第n-1个月的多,则需要本月需要(need[n]-need[n-1])*hire+need[n]*salary的钱
如果第n个月的需要的人数比第n-1个月的少,则需要本月需要(need[n-1]-need[n])*fire+need[n]*salary的钱
假设第n-1个月雇佣k个人是最有子结构;
则状态方程:dp[i][j]=dp[i][k]+(need[n]-need[n-1])*hire+need[n]*salary
或dp[i][j]=dp[i][k]+(need[n-1]-need[n])*fire+need[n]*salary
code:
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int INF = 0x7fffffff; int hire,salary,fire; int need[15],dp[15][505]; int main() { int n,mini,maxn,ans; while(scanf("%d",&n)&&n) { maxn=0; scanf("%d %d %d",&hire,&salary,&fire); for(int i=1;i<=n;i++) { scanf("%d",&need[i]); maxn=max(maxn,need[i]); } if(maxn==0) { printf("0\n"); continue; } memset(dp,0,sizeof(dp)); for(int i=need[1];i<=maxn;i++) { dp[1][i]=(hire+salary)*i; } int temp; for(int i=2;i<=n;i++) { for(int j=need[i];j<=maxn;j++) { mini=INF; for(int k=need[i-1];k<=maxn;k++) { if(j>=k) { temp=dp[i-1][k]+(j-k)*hire+j*salary; } else { temp=dp[i-1][k]+(k-j)*fire+j*salary; } mini=min(mini,temp); } dp[i][j]=mini; } } ans=INF; for(int i=need[n];i<=maxn;i++) { if(ans>dp[n][i]) ans=dp[n][i]; } printf("%d\n",ans); } return 0; }
相关推荐
关于hdu的动态规划的题目,包括一些水题,还有一些经典的动态规划题目。
HDU 动态规划(46道题目
动态规划DP题解 POJ HDU部分动态规划DP题解
hdu动态规划算法集锦
HDU的一题........HDU DP动态规
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
HDU动态规划,此PPT系杭州电子科技大学ACM总教练刘春英老师所有, 特在此分享贡献给广大编程爱好者, 特别是ACMer!
杭电ACM课件2014版之 (HDUACM201403版_05)动态规划
动态规划DP题解 POJ HDU 动态规划解题报告
算法设计与分析实验六:使用动态规划算法解决存钱问题(java实现、hdu1114)(csdn)————程序
这是一个相当齐全的算法课件 里面包含了很多的内容和实例 使我们上课时老师的课件 希望对大家有帮助
动态规划入门,hdu上的动态规划入门题的结题报告。 hdu 1171,hdu 1059,hdu 2159,hdu 2191,hdu 3496
(lecture_04)动态规划(1)_ (lecture_05)计算几何基础_ (lecture_06)母函数 (lecture_7)特殊的数 (lecture_8)组合博弈入门 (lecture_09贪心算法 (lecture_11)搜索入门 (lecture_12)二分匹配及其应用 ...
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
动态规划 杭电 课程 课件 详细解析 HDU
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门