2061.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 2061 on 2006-02-16 at 01:51:08 */ 
#include <cstdio>
#include <algorithm>
#include <climits>
using namespace std;

const int MAX = 1024;
typedef unsigned int uint;

class Section {
public:
	int x, cost, delta;
	void make();
	void set(int);
	bool operator <(const Section&) const;
};
void Section::make() {
	scanf("%d %d %d", &x, &cost, &delta);
}
void Section::set(int cx) { 
	x = cx; cost = delta = 0;
}
bool Section::operator <(const Section& s) const {
	return x < s.x;
}

uint cost[MAX][MAX][2], sum[MAX][MAX];

int main()
{
	int i, j, n, gwarr;
	Section sect[MAX], robot;

	while(scanf("%d %d", &n, &gwarr) != EOF && n != 0) {
		robot.set(gwarr);
		int delta = 0, bc = 0;
		for(i = 0; i < n; i++) sect[i].make(), delta += sect[i].delta, bc += sect[i].cost;
		sect[n++] = robot; sort(sect, sect+n);
		int b = lower_bound(sect, sect+n, robot) - sect;
		for(i = 0; i < n; i++)
			for(j = i; j < n; j++)
				if(i == j) sum[i][j] = sect[i].delta;
				else sum[i][j] = sum[i][j-1]+sect[j].delta;
		for(i = b; i >= 0; i--)
			for(j = b; j < n; j++)
				if(i == b && j == b) cost[b][b][0] = cost[b][b][1] = 0;
				else {
					cost[i][j][0] = cost[i][j][1] = INT_MAX;
					if(i != b) cost[i][j][0] = cost[i+1][j][0]+(delta-sum[i+1][j])*(sect[i+1].x-sect[i].x);
					if(j != b) cost[i][j][1] = cost[i][j-1][1]+(delta-sum[i][j-1])*(sect[j].x-sect[j-1].x);
					int step = (delta-sum[i][j])*(sect[j].x-sect[i].x);
					cost[i][j][0] = min(cost[i][j][0], cost[i][j][1]+step);
					cost[i][j][1] = min(cost[i][j][1], cost[i][j][0]+step);
				}
		printf("%u\n", cost[0][n-1][0]+bc);
	}

	return 0;
}