UVA11400 - Lighting System Design

この問題は、まず電球を電圧によって小から大に並べ替える、シーケンス中の1つの電球iが、m個の電球がiに変換可能であれば、その電球は必ずiの前にあり、このm個の電球は連続的にiの前に隣接しているので、何個の電球がiに変換可能であるかを列挙する、dp[i]の最小値を求めることができる.dp[i] = min(dp[i], (sum[i] - sum[j]) * lamp[i].c + dp[j] + lamp[i].k); では、なぜこのm個の電球は連続しているのでしょうか.電球a,b,c,dがあれば,それらの価格はq 1,q 2,q 3,q 4であり,aとcがd,bに変換可能であれば,q 2#include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #include<cmath> #include<queue> #include<iostream> using namespace std; #define INF 1 << 30 struct Lamp{ int v, k, c, l; }lamp[1005]; int sum[1005], dp[1005]; int cmp(const Lamp &a, const Lamp &b) { return a.v < b.v; } int main() { //freopen("in.txt", "r", stdin); int n; while(cin >> 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+n+1, cmp); sum[0] = 0; for(int i =1; i <= n; i++) sum[i] = sum[i-1] + lamp[i].l; 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], (sum[i] - sum[j]) * lamp[i].c + dp[j] + lamp[i].k); } } cout << dp[n] << endl; } return 0; }