1456 transportation.cpp

ACM 威士忌部分答案

#include <cstdio>
#include <algorithm>
using namespace std;

int n; 
int m; 
int t;

struct order
{
	int from; 
	int to; 
	int pass;
	int price; 
	int get;
	bool operator < (const order & t) const
	{
		return price>t.price;
	}
}orders[32];
int train[16];

int mmax;

void dfs(int s, int earn) 
{
	//printf("---- %d %d\n",s,earn);
	bool flag;
	int i;
	
	if(earn > mmax)
		mmax = earn;

	for( ; s < t; s++)
	{
		flag=false;
		if(earn + orders[s].get < mmax)
			return;

		for(i = orders[s].from; i < orders[s].to; i++)
		{
			train[i] += orders[s].pass;
			if( train[i]  > n)
			{
				flag=true;
				break;
			}
		}
		if(!flag)
		{
			dfs(s + 1, earn + orders[s].price);
			i--;	
		}

		for( ; i >= orders[s].from; i--)
			train[i] -= orders[s].pass;
	}
}

int main(void)
{
	int i;

	while(scanf("%d%d%d", &n, &m, &t)==3)
	{
		if(n==0 && m==0 && t==0) 
			break;

		for(i = 0; i < t; i++)
		{
			scanf("%d%d%d", &orders[i].from, &orders[i].to, &orders[i].pass);
			orders[i].price = (orders[i].to - orders[i].from) * orders[i].pass;
			orders[i].get=0;
		}

		sort(orders,orders+t);

		for(i = t - 1; i >= 0; i--)
			orders[i].get =  orders[i+1].get + orders[i].price;

		memset(train, 0, sizeof(train));

		mmax = 0;

		dfs(0, 0);

		printf("%d\n", mmax);
	}
	return 0;
}