电源

UVa 11400 - Lighting System Design（DP）

2019-07-14 02:03发布

站内文章 / 电源技术
13205 0 1537
为了使所用费用最少， 那么最优的选择是直选一种，这样只需要一种电源的钱。 #include #include using namespace std; const int INF = 2000000000; const int maxn = 1111; struct Lamp { int V, K, C, L; bool operator < (const Lamp&k) const { return V < k.V; } }l[maxn]; int s[maxn], d[maxn]; int main() { int n; while(cin >> n && n) { fill(d + 1, d + n + 1, INF); for(int i = 1; i <= n; i++) { cin >> l[i].V >> l[i].K >> l[i].C >> l[i].L; } sort(l + 1, l + n + 1); for(int i = 1; i <= n; i++) { s[i] = s[i - 1] + l[i].L; } for(int i = 1; i <= n; i++) { for(int j = 0; j <= i; j++) { d[i] = min(d[i], d[j] + (s[i] - s[j]) * l[i].C + l[i].K); } } cout << d[n] << endl; } return 0; }

热门文章