[BZOJ 3112][ZJOI 2013] 防守战线

题目大意

长为 \(n\) 的序列,第 \(i\) 位上建一座塔需花费 \(c_i\),每个位置可建多座塔,有 \(m\) 个区间,第 \(i\) 个区间内至少要有 \(d_i\) 座塔,球最小花费。

\(1 \leqslant n \leqslant 1,000\)

\(1 \leqslant m, \ c_i, \ d_i \leqslant 10,000\)

题目链接

BZOJ 3112题面

CodeVS 1618

题解

裸题。

单纯形,对偶原理。

代码

注意答案会超过 int

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <cstdio>
#include <cfloat>
#include <algorithm>
const int MAXN = 1005;
const int MAXM = 10005;
const double EPS = 1e-7;
struct LinearPlanning {
double A[MAXN][MAXM], b[MAXN], c[MAXM], v;
int n, m;
void pivot(int l, int e) {
b[l] /= A[l][e];
for (int i = 1; i <= m; i++) if (i != e) A[l][i] /= A[l][e];
A[l][e] = 1 / A[l][e];
for (int i = 1; i <= n; i++) {
if (i != l && abs(A[i][e]) > EPS) {
b[i] -= A[i][e] * b[l];
for (int j = 1; j <= m; j++) if (j != e) A[i][j] -= A[i][e] * A[l][j];
A[i][e] = -A[i][e] * A[l][e];
}
}
v += c[e] * b[l];
for (int i = 1; i <= m; i++) if (i != e) c[i] -= c[e] * A[l][i];
c[e] = -c[e] * A[l][e];
}
double operator()(int n, int m) {
this->n = n;
this->m = m;
while (true) {
int i;
for (i = 1; i <= m; i++) if (c[i] > EPS) break;
int e = i;
if (e == m + 1) return v;
double temp = DBL_MAX;
int l;
for (i = 1; i <= n; i++) if (A[i][e] > EPS && b[i] / A[i][e] < temp) temp = b[i] / A[i][e], l = i;
if (temp == DBL_MAX) return DBL_MAX;
pivot(l, e);
}
}
} lp;
int main() {
int n, m;
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%lf", &lp.b[i]);
for (int i = 1; i <= m; i++) {
int l, r, d;
scanf("%d %d %d", &l, &r, &d);
for (int j = l; j <= r; j++) lp.A[j][i] = 1;
lp.c[i] = d;
}
printf("%lld\n", (long long) (lp(n, m) + 0.5));
return 0;
}