1158.cpp

杭电 acm部分代码 有兴趣的可以下载 谢谢

#include<iostream>
#include<climits>
using namespace std;
int a[12];
int dp[12][1001];
int fire,hire,salary,mini;
int trans(int a,int b){
    if(b>=a)
        return (b-a)*hire+b*salary;
    else
        return (a-b)*fire+b*salary;
}
void main()
{

    int n,i,j,k,max;
    while(cin>>n){
        if(!n)  break;
        max=0;
        cin>>hire>>salary>>fire;
        for(i=0;i<n;i++){
            cin>>a[i];
            if(max<a[i])    max=a[i];
        }
        for(j=a[0];j<=max;j++)
            dp[0][j]=j*(hire+salary);
        for(i=1;i<n;i++)
            for(j=a[i];j<=max;j++){
            dp[i][j]=INT_MAX;
            for(k=a[i-1];k<=max;k++)
                if(dp[i-1][k]+trans(k,j)<dp[i][j])
                    dp[i][j]=dp[i-1][k]+trans(k,j);
        }
        mini=dp[n-1][a[n-1]];
        for(i=a[n-1]+1;i<=max;i++)
            if(dp[n-1][i]<mini)  mini=dp[n-1][i];
        cout<<mini<<endl;
    }
}