题意

有n种灯，每种灯分别需要电压v，电压为v的电源k元，每个灯c元，一共需要l个灯。为了节约电源费用，可以用高电压灯代替低电压灯。求采购灯和电源的最低费用。

题解

首先对灯按电压进行排序，dp[i]为0-i盏灯所需要的最低费用，递推dp[i]=min(dp[j]+(d[i]-d[j])*lt[i].c+lt[i].k,dp[i])，lt[i].c为第i盏灯所需要的单价，lt[i].k为第i盏灯电源费用。进行O(n^2)次循环，即可得解。

注意事项

注意dp[0]=0初始化问题

代码

#include #include #include #define INF 1e9 using namespace std; int dp[1010],d[1010]; typedef struct{ int v,k,c,l; }Light; bool cmp(Light a,Light b){ if(a.v>b.v) return false; else return true; } Light lt[1010]; int main() { //freopen("d://input.txt","r",stdin); //freopen("d://output.txt","w",stdout); int n; while(scanf("%d",&n)){ if(n==0) break; for(int i=1;i<=n;i++){ scanf("%d%d%d%d",&lt[i].v,&lt[i].k,&lt[i].c,&lt[i].l); } sort(lt,lt+n+1,cmp); for(int i=1;i<=n;i++){ dp[i]=INF; } d[0]=0; for(int i=1;i<=n;i++){ d[i]=d[i-1]+lt[i].l; //printf("%d ",d[i]); } dp[0]=0; for(int i=1;i<=n;i++){ for(int j=0;j<=n;j++){ if(i>j){ //printf("%d %d %d %d %d %d ",i,j,min(dp[j]+(d[i]-d[j])*lt[i].c+lt[i].k,dp[i]),lt[i].k,lt[i].c,dp[i]); dp[i]=min(dp[j]+(d[i]-d[j])*lt[i].c+lt[i].k,dp[i]); } } } printf("%d ",dp[n]); } return 0; }