题目链接：
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2395
题意：要安装n种灯，每种灯给出价格C，需要安装数量L个，然后每种灯需要一个电源，给出每种灯需要的电源功率V，电源的价格，那么可以得到安装的花费，但是对应第功率的灯可以用高功率的灯替换，让求出最小的安装价格。
解析：由于高功率的灯一定能替换低功率的灯，所以将灯按功率从小到大排序，那么后面的灯一定能替换前面的灯；
然后有下状态转移方程：dp[i]=min(dp[i],dp[j]+lamp[i].K+lamp[i].C*(sumL[i]-sumL[j]))；（j<i）
意思是用当前的第i种灯替换[j+1,i]区间中的所有灯。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll M=1005;int n,dp[M];
int sumL[M];
struct Node{int V,K,C,L;bool operator < (const Node & obj)const{ return V<obj.V; }
}lamp[M];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);for(int i=1;i<=n;i++)//灯的数量的前缀和{sumL[i]=sumL[i-1]+lamp[i].L;}memset(dp,0x7f,sizeof(dp));dp[0]=0;for(int i=1;i<=n;i++){for(int j=0;j<i;j++){dp[i]=min(dp[i],dp[j]+lamp[i].K+lamp[i].C*(sumL[i]-sumL[j]));}}printf("%d\n",dp[n]);}return 0;
}