uva11400 动态规划

没种电压灯泡要么全换，要么不换。状态d(i)表示前i种灯泡的最低价格。

转移方程：

dp[i]=min(dp[i],dp[j]+(s[i]-s[j])*d[i].c+d[i].k);

AC代码：

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=1000+5;
const int INF=1<<30;
struct node{
    int v,k,c,l;
    bool operator < (const node&p) const{
        return v<p.v;
    }
};
node d[maxn];
int s[maxn],dp[maxn];
int main(){
    int n;
    while(scanf("%d",&n)==1&&n){
        for(int i=1;i<=n;++i){
            scanf("%d%d%d%d",&d[i].v,&d[i].k,&d[i].c,&d[i].l);
        }
        sort(d+1,d+n+1);
        s[0]=0;
        for(int i=1;i<=n;++i){
            s[i]=d[i].l+s[i-1];
        }
        for(int i=1;i<=n;++i){
            dp[i]=INF;
            for(int j=0;j<i;++j){
                dp[i]=min(dp[i],dp[j]+(s[i]-s[j])*d[i].c+d[i].k);
            }
        }
        printf("%d\n",dp[n]);
    }
    return 0;
}

如有不当之处欢迎指出！

巴特西

uva11400 动态规划

最新文章

热门文章