Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 4846 Accepted Submission(s): 2061
#include<iostream> #include<cstdio> #include<cstring> using namespace std; #define INF 999999999 int mon[15]; int dp[15][10000]; int main() { int n,hire,fire,sala; while(scanf("%d",&n)!=EOF&&n) { //memset(dp,0,sizeof(dp)); scanf("%d%d%d",&hire,&sala,&fire); int maxn=0; for(int i=1; i<=n; i++) { scanf("%d",&mon[i]); if(maxn<mon[i]) maxn=mon[i]; } for(int i=1; i<=12; i++) for(int j=0; j<=10000; j++) dp[i][j]=INF; for(int i=1; i<=n; i++) for(int j=mon[i]; j<=maxn; j++) if(i==1) dp[i][j]=j*(sala+hire); else { for(int k=mon[i-1]; k<=maxn; k++) if(j>=k) dp[i][j]=min(dp[i][j],dp[i-1][k]+(j-k)*(sala+hire)+k*sala); else dp[i][j]=min(dp[i][j],dp[i-1][k]+(k-j)*fire+j*sala); } //cout<<dp[1][10]<<‘*‘<<dp[1][11]<<endl; // cout<<dp[2][9]<<‘*‘<<dp[2][10]<<‘*‘<<dp[2][11]<<endl; // cout<<dp[3][11]<<endl; int ans=INF; for(int i=mon[n]; i<=maxn; i++) if(ans>dp[n][i]) ans=dp[n][i]; printf("%d\n",ans); } return 0; }
原文:http://www.cnblogs.com/jasonlixuetao/p/5491222.html