电源

UVA 11400 Lighting System Design (DP)

2019-07-14 02:51发布

站内文章 / 电源技术
12460 0 1526
题意：给出一些灯泡，每个灯泡有四个参数，电压，所需电源价格，当前灯泡价格，需要购买的数量。还有一些条件，为了省钱，低电压的灯泡可以替换成高电压的灯泡，每种灯泡都只能对应唯一的电源，不同的灯泡之间是不能互相使用电源的。 解法：题目还是相对简单的，首先我们用前缀和得到前n种灯泡的数量，且显然，如果一种灯泡要转为更高电压的灯泡，肯定是全部一起转的。我们不断枚举区间，代表这个区间的灯泡都用第i种灯泡。然后dp[i] = min(dp[i], dp[j - 1] + (cnt[i] - cnt[j - 1]) * c[i] + k[i]) 代码如下： #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; const int maxn = 1005; const int INF = 0x3f3f3f3f; int dp[maxn], cnt[maxn]; struct NODE { int v, k, c, l; bool operator < (const NODE &t) const { if(v < t.v) return 1; return 0; } }light[maxn]; int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); #endif int n; while(scanf("%d", &n) != EOF) { if(n == 0) break; 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); for(int i = 1; i <= n; i++) cnt[i] = cnt[i - 1] + light[i].l; for(int i = 1; i <= n; i++) { dp[i] = INF; for(int j = 1; j <= i; j++) { dp[i] = min(dp[i], dp[j - 1] + (cnt[i] - cnt[j - 1]) * light[i].c + light[i].k ); } } printf("%d ", dp[n]); } return 0; }

热门文章