www.b2bchain.cn

# Volunteer recruitment

### Description

Suppose you will recruit a group of volunteers for a coming event. It is estimated that this event will take N days to complete, and the i(th) day needs at least Ai volunteers. The number of kinds of volunteers is M. The volunteers of i(th) kind can volunteer from the Si day to the Fi day and the recruit fee is Ci. In order to do his job well, you hope to recruit enough volunteers with least money. Please give an optimal plan.

note: i(th) means the ordinal of this number is i

### Input

The first line presents two integers: N, M. The second line contains N nonnegative integers presenting the numbers of volunteers each day needs. Each of the other lines contain three integers: Si, Fi, Ci

note: You can recruit each kind of volunteers as many as possible.

### Output

Just a number meaning the total money of your optimal plan.

3 3

2 3 4

1 2 2

2 3 5

3 3 2

14

### Hint

1<=N<=200, 1<=M<=1000, 题目中所有数据不超过2^31-1

` `#include <iostream> #include <cmath> #define N 1010 #define M 10100 using namespace std; const double INF = 1e10; const double eps = 1e-7; int n, m; double A[M][N], b[M], c[N], v; void Pivot(int l, int e) { 	b[l] /= A[l][e]; 	for (int i = 1; i <= n; i++) 		if (i != e) 			A[l][i] /= A[l][e]; 	A[l][e] = 1 / A[l][e]; 	for (int i = 1; i <= m; i++) 		if (i != l && fabs(A[i][e])>eps) 		{ 			b[i] -= A[i][e] * b[l]; 			for (int 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 (int 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 (true) 	{ 		for (i = 1; i <= n; i++) 			if (c[i]>eps) break; 		if ((e = i) == n + 1) return v; 		double tmp = INF; 		for (i = 1; i <= m; i++) 			if (A[i][e]>eps && b[i] / A[i][e]<tmp) 				tmp = b[i] / A[i][e], l = i; 		if (tmp == INF) return INF; 		Pivot(l, e); 	} } int main() { 	cin >> n >> m; 	for (int i = 1; i <= n; i++) cin>>c[i]; 	for (int i = 1, x, y; i <= m; i++) 	{ 		cin>>x>>y>>b[i]; 		for (int j = x; j <= y; j++) 			A[i][j] = 1; 	} 	double ans = Simplex(); 	cout<< int(ans + 0.5); 	return 0; } ``

• 微信咨询
• 回顶