2767.cpp

ACM北京赛区比赛的试题源码,在PKU在线评测可以通过.

#include <iostream.h>
#include <string.h>

char v[10];
int h[10];
int r[10];
int R[10];
int n;
float best;
float ht[11];
int bow[11];

void Solve(int k)
{
	if (k == n+1) //all processed
	{
		float t = -1;
		for(int i=1;i<=n;i++) if (h[bow[i]]+ht[i]>t) t = h[bow[i]]+ht[i];//这里是bug,只考虑了最后一个,但其实前面几个可能比最后一个还高.
		if (t<best) best = t;
		return;
	}
	int i,j;
	float m_ht[11];
	float t;
	for(i=1;i<=n;i++) if (!v[i]) 
	{
		v[i] = 1;
		bow[k] = i;
		m_ht[0] = 0;
		for(j=1;j<k;j++) 
		{
			m_ht[j] = -1;
			//r
			if (r[i]>=R[bow[j]]) 
				m_ht[j] = m_ht[j]>=(ht[j]+h[bow[j]])?m_ht[j]:(ht[j]+h[bow[j]]);
			if (r[i]<=r[bow[j]]) 
				m_ht[j] = m_ht[j]>=ht[j]?m_ht[j]:ht[j];
			if (r[i]<R[bow[j]] && r[i]>r[bow[j]]) 
			{
				t = (r[i]-r[bow[j]])*1.0/(R[bow[j]]-r[bow[j]])*h[bow[j]]+ht[j];
				m_ht[j] = m_ht[j]>=t?m_ht[j]:t;
			}
			//R
			if (R[i]<=r[bow[j]]) 
				m_ht[j] = m_ht[j]>=ht[j]?m_ht[j]:ht[j];
			if (R[i]>r[bow[j]] && R[i]<=R[bow[j]]) 
			{
				t = (R[i]-r[bow[j]])*1.0/(R[bow[j]]-r[bow[j]])*h[bow[j]]+ht[j]-h[i];
				m_ht[j] = m_ht[j]>=t?m_ht[j]:t;
			}
			if (R[i]>R[bow[j]]) 
			{
				if (r[i]>=R[bow[j]]) continue;
				t = ht[j]+h[bow[j]]-(R[bow[j]]-r[i])*1.0/(R[i]-r[i])*h[i];
				m_ht[j] = m_ht[j]>t?m_ht[j]:t;
			}
		}
		ht[k] = -1;
		for(j=0;j<k;j++) ht[k] = ht[k]>m_ht[j]?ht[k]:m_ht[j];
		Solve(k+1);
		v[i] = 0;
	}
}


int main()
{
	int T;
	int i;
	cin>>T;
	while(T--)
	{
		cin>>n;
		for(i=1;i<=n;i++) cin>>h[i]>>r[i]>>R[i];
		ht[0] = 0;
		h[0] = 0;
		R[0] = 0;
		r[0] = 0;
		bow[0] = 0;
		best = 1000000.0;
		Solve(1);
		cout<<(int)best<<endl;
	}
	return 0;
}