Description

　　申奥成功后，布布经过不懈努力，终于成为奥组委下属公司人力资源部门的主管。布布刚上任就遇到了一个难
题：为即将启动的奥运新项目招募一批短期志愿者。经过估算，这个项目需要N 天才能完成，其中第i 天至少需要
Ai 个人。 布布通过了解得知，一共有M 类志愿者可以招募。其中第i 类可以从第Si 天工作到第Ti 天，招募费用
是每人Ci 元。新官上任三把火，为了出色地完成自己的工作，布布希望用尽量少的费用招募足够的志愿者，但这
并不是他的特长！于是布布找到了你，希望你帮他设计一种最优的招募方案。
Input
　　第一行包含两个整数N, M，表示完成项目的天数和可以招募的志愿者的种类。 接下来的一行中包含N 个非负
整数，表示每天至少需要的志愿者人数。 接下来的M 行中每行包含三个整数Si, Ti, Ci，含义如上文所述。为了
方便起见，我们可以认为每类志愿者的数量都是无限多的。
Output

　　仅包含一个整数，表示你所设计的最优方案的总费用。
Sample Input
3 3

2 3 4

1 2 2

2 3 5

3 3 2
Sample Output
14
HINT

1 ≤ N ≤ 1000，1 ≤ M ≤ 10000，题目中其他所涉及的数据均 不超过2^31-1。

解题方法： 裸单纯形， 这里推荐一下wyfcyx的《线性规划与单纯形算法》

http://wenku.baidu.com/view/ce5784754a7302768f99391d

这里设志愿者数量的向量为X , 每天需要人数的向量为Y , 目标最小值的系数向量为C , 便可以得到一个最小化目标值的线性规划：
AX≥Y 求 MIN(CX)
把对应出的系数矩阵带入到单纯形算法就可以求出最优解了。
复杂度 ： O(玄学)
代码如下：

#include <bits/stdc++.h>
using namespace std;
#define INF 1e10
#define EPS 1e-7
int n, m;
namespace Linear_Programming{
    double A[10100][1010],b[10100],c[1010],v;
    void Pivot(int l,int e)
    {
        int i,j;

        b[l]/=A[l][e];
        for(i=1;i<=n;i++)
            if(i!=e)
                A[l][i]/=A[l][e];
        A[l][e]=1/A[l][e];

        for(i=1;i<=m;i++)
            if(i!=l&&fabs(A[i][e])>EPS)
            {
                b[i]-=A[i][e]*b[l];
                for(j=1;j<=n;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(i=1;i<=n;i++)
            if(i!=e)
                c[i]-=c[e]*A[l][i];
        c[e]=-c[e]*A[l][e];
    }
    double Simplex()
    {
        int i,l,e;
        while(1)
        {
            for(i=1;i<=n;i++)
                if(c[i]>EPS)
                    break;
            if((e=i)==n+1)
                return v;
            double temp=INF;
            for(i=1;i<=m;i++)
                if( A[i][e]>EPS && b[i]/A[i][e]<temp )
                    temp=b[i]/A[i][e],l=i;
            if(temp==INF) return INF;
            Pivot(l,e);
        }
    }
}

int main(){
    using namespace Linear_Programming;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) scanf("%lf", &c[i]);
    for(int i = 1; i <= m; i++){
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        for(int j = x; j <= y; j++){
            A[i][j] = 1;
        }
        b[i] = z;
    }
    double ans = Simplex();
    printf("%d\n", (int)(ans + 0.5));
    return 0;
}