题目链接:
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;
}