题目
战线可以看作一个长度为(n)的序列，现在需要在这个序列上建塔来防守敌兵，在序列第(i)号位置上建一座塔有(C_i)的花费，且一个位置可以建任意多的塔，费用累加计算。有(m)个区间([L_1,R_1],[L_2,R_2],…,[L_m,R_m])，在第(i)个区间的范围内要建至少(D_i)座塔。求最少花费。
算法1——费用流
我们会发现这题很像Noi2008 志愿者招募。
但是两式相减之后却不能产生想[志愿者招募]一样的效果，原因是对于一个区间，它体现在矩阵里面的系数不是在同一列，而是在同一行。
有个神奇的东西，就是转换成这个问题的对偶问题。对偶问题怎么转换呢，链接。
对于原问题 可以描述为：
有一个工厂，它生产(n)种产品，第(i)种产品可以卖(c_i)元
现在一共有(m)种材料 生产一个产品(i)需要(a_{ij})个材料(j)
每个材料的个数有上限 为(b_i)
现在要求一种生产方案使得获利最多
这个问题的对偶问题 可以描述为：
你现在要找这个工厂购买原材料 第(i)种材料需要(b_i)个 价格由你定
这个工厂会把材料卖给你 仅当它觉得不亏
即它把卖给你的材料拿去做产品的价值(leq)你收购做这个产品所需材料的价格和
求最少需要多少钱可以收购完
我觉得这个“证明”好形象！
然后我们就可以像[志愿者招募]一样构图，接着用跑费用流了，但是最“原始”的费用流会被卡掉(3)个点，所以我们要用(zkw)网络流！
一开始我有点担心图中会不会出现正圈，lzh教导我：如果原图没有正圈，那么残余网络中也不会有正圈！
算法2——单纯形
这个单纯形，我弄了一整个早上才明白。
这里是维基的资料。
关于单纯形，什么时候我们能跑整数的呢（在这题里面，矩阵里的元素只有(-1,0,1)）？想到省赛就要来了，先把这个问题放一放。贴吧里有个帖子就是讨论这个的。
贴个代码，虽然不需要用double，但我还是先写个标准的单纯形吧。
#include <cstdio>
#include <cmath>
#include <iostream>
#include <assert.h>
using namespace std;
const int MAXN = 1003;
const int MAXM = 10003;
const double INF = 1e100;
const double EPS = 1e-8;
int n, m;
double A[MAXN][MAXM];
int main() {
freopen("defend.in", "r", stdin);
freopen("defend.out", "w", stdout);
scanf("%d%d", &n, &m);
n ++, m ++;
for (int i = 1; i < n; i ++) {
scanf("%lf", A[i] + m);
}
for (int i = 1; i < m; i ++) {
int L, R;
scanf("%d%d%lf", &L, &R, A[n] + i);
for (int j = L; j <= R; j ++)
A[j][i] = 1;
}
while (true) {
int x = -1, y;
for (int i = 1; i < m; i ++) {
if (A[n][i] - EPS <= 0) continue;
x = i;
y = -1;
double tval = INF;
for (int j = 1; j < n; j ++) {
if (A[j][i] - EPS <= 0) continue;
double tmp = A[j][m] / A[j][i];
if (tmp < tval) {
tval = tmp;
y = j;
}
}
assert(y != -1);
break;
}
if (x == -1) break;
for (int i = 1; i <= m; i ++)
if (i != x) A[y][i] /= A[y][x];
A[y][x] = (double) 1 / A[y][x];
for (int i = 1; i <= n; i ++)
if (fabs(A[i][x]) > EPS)
for (int j = 1; j <= m; j ++)
if (i != y && j != x)
A[i][j] -= A[i][x] * A[y][j];
for (int i = 1; i <= n; i ++)
if (i != y) A[i][x] *= - A[y][x];
}
printf("%.0lf
", (double) - A[n][m]);
return 0;
}