UVa 11400 Lighting System Design(DP)

标题:ある場所の照明システムを設計するには全部でn種類の異なるタイプの電球が必要で、次に各電球の電圧vを入力して電圧電源の価格k各電球の価格cこのような電球の数lの電圧の低い電球が必要で、電圧高の電球で各電球を交換することができて、1つの対応する電源だけが必要でこの写真を完成します明システムの最小コスト
dp、多段階決定、電圧を並べ替えると、小さいものは大きいものに変えることができ、各段階iに対して、i種類の決定があり、2つのdp方向はいずれも可能である.

//0 KB 145 ms
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int n;
int dp[1010];
int sum[1010];
struct node
{
    int v,k,c,l;
}lamp[1010];
bool cmp(const node&a,const node&b)
{
    if(a.v==b.v) return a.k<b.k;//       ，         ，    
    return a.v>b.v;
}
int main()
{
    while(scanf("%d",&n),n){
        for(int i=1;i<=n;i++){
            scanf("%d%d%d%d",&lamp[i].v,&lamp[i].k,&lamp[i].c,&lamp[i].l);

        }
        sort(lamp+1,lamp+1+n,cmp);
        for(int i=1;i<=n;i++) sum[i]=sum[i-1]+lamp[i].l;
        dp[1]=lamp[1].c*lamp[1].l+lamp[1].k;
        for(int i=2;i<=n;i++){
            int cos=lamp[i].c,num=lamp[i].l,pow=lamp[i].k;
            dp[i]=cos*num+pow+dp[i-1];
            for(int j=1;j<i;j++){
                cos=lamp[j].c,pow=lamp[j].k;
                dp[i]=min(dp[i],dp[j-1]+(sum[i]-sum[j-1])*cos+pow);
            }
        }
        printf("%d
",dp[n]);
    }
    return 0;
}

//0 KB 139 ms
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int n;
int dp[1010];
int sum[1010];
struct node
{
    int v,k,c,l;
}lamp[1010];
bool cmp(const node&a,const node&b)
{
    return a.v<b.v;
}
int main()
{
    while(scanf("%d",&n),n){
        for(int i=1;i<=n;i++){
            scanf("%d%d%d%d",&lamp[i].v,&lamp[i].k,&lamp[i].c,&lamp[i].l);

        }
        sort(lamp+1,lamp+1+n,cmp);
        for(int i=1;i<=n;i++) sum[i]=sum[i-1]+lamp[i].l;
        dp[1]=lamp[1].c*lamp[1].l+lamp[1].k;
        for(int i=2;i<=n;i++){
            int cos=lamp[i].c,num=lamp[i].l,pow=lamp[i].k;
            dp[i]=cos*num+pow+dp[i-1];
            for(int j=1;j<i;j++){
                dp[i]=min(dp[i],dp[j-1]+(sum[i]-sum[j-1])*cos+pow);
            }
        }
        printf("%d
",dp[n]);
    }
    return 0;
}