紫皮书题：
题意：让你设计照明系统，给你n种灯泡，每种灯泡有所需电压，电源，每个灯泡的费用，以及每个灯泡所需的数量。每种灯泡所需的电源都是不同的，其中电压大的灯泡可以替换电压小的灯泡，要求求出最小费用
题解：每种电压灯泡要么全换，要么全不换，因为只换部分还要加额外的电源费用，并且换了部分之后费用更少，不如全换
先把灯泡按照电压从小到大排序，这样进行dp时，后面的电压大的如果比电压小的更优的话就可以替换了
设dp[j]为前j个最优了，则dp[i] = min{dp[i],dp[j] + (s[i]-s[j]) * c[i] + k[i]} dp[i]在使用前要初始化为最大
s为前i种灯泡的总数量，s[i] - s[j]表示从 i 到 j 替换为 i 则费用为 (s[i] - s[j]) * c[i] + k[i] 还要加上前 j 个灯泡的费用 dp[j];
#include <iostream> #include <algorithm> #include <cmath> #include <cstring> #include <cstdio> #include <cstdlib> const int INF = 0xfffffff; const double ESP = 10e-8; const double Pi = atan(1) * 4; const int MOD = 1000007; const int MAXN = 1000 + 10; typedef long long LL; using namespace std; struct Light{ int v,k,c,l; bool operator < (Light a)const{ return v < a.v; } }; Light light[MAXN]; LL dp[MAXN]; LL s[MAXN]; int main(){ // freopen("input.txt","r",stdin); int n; while(~scanf("%d",&n) && n){ for(int i = 1;i <= n;i++){ scanf("%d%d%d%d",&light[i].v,&light[i].k,&light[i].c,&light[i].l); } sort(light+1,light+n+1); s[0] = 0; for(int i = 1;i <= n;i++){ s[i] = light[i].l + s[i-1]; } dp[0] = 0; 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]) * light[i].c + light[i].k); } } printf("%lld\n",dp[n]); } return 0; }
uva 11400 Problem F Lighting System Design
原文：http://www.cnblogs.com/hanbinggan/p/4374741.html