首页 > 代码库 > zoj 1454 Employment Planning
zoj 1454 Employment Planning
【题解】:
【代码】:
1 #include <iostream> 2 #include <string.h> 3 #include <stdio.h> 4 #include <algorithm> 5 #include <stdlib.h> 6 #define LL long long 7 using namespace std; 8 LL dp[15][100005]; 9 LL N,h,uh,sal,num[15]; 10 LL max(LL a,LL b){ 11 if (a>b) return a;else return b; 12 } 13 LL min(LL a,LL b){ 14 if (a<b) return a;else return b; 15 } 16 int main(){ 17 while(cin>>N && N>0){ 18 cin>>h>>sal>>uh; 19 int MaxN=-1; 20 for(int i=1;i<=N;i++) { 21 cin>>num[i]; 22 MaxN=max(MaxN,num[i]); 23 } 24 for(int i=0;i<=N;i++){ 25 for(int j=0;j<=MaxN;j++) dp[i][j]=99999999; 26 } 27 for(int i=num[1];i<=MaxN;i++) dp[1][i]=i*(h+sal); 28 for(int i=2;i<=N;i++){ 29 for(int j=num[i];j<=MaxN;j++){ 30 for(int k=0;k<=MaxN;k++){ 31 if (k<num[i-1]) continue; 32 if (k==j) dp[i][j]=min(dp[i][j],dp[i-1][k]+sal*j); 33 if (k<j) dp[i][j]=min(dp[i][j],dp[i-1][k]+sal*j+h*(j-k)); 34 if (k>j) dp[i][j]=min(dp[i][j],dp[i-1][k]+sal*j+uh*(k-j)); 35 } 36 // cout<<"i="<<i<<","<<"j="<<j<<":" ; 37 // cout<<dp[i][j]<<endl; 38 } 39 } 40 int ans=99999999; 41 for(int i=num[N];i<=MaxN;i++) ans=min(ans,dp[N][i]); 42 cout<<ans<<endl; 43 } 44 return 0; 45 }
//错误是注意检查初值、边界
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。