Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM-ICPC竞赛训练》暑期课面向全球招生。容量有限,报名从速!

谢谢,用这数据找到了程序问题,一次AC,也奉献社会,贴代码

Posted by lsz at 2011-05-11 21:14:24 on Problem 1661
In Reply To:也奉献社会,这组数据过了肯定AC!! Posted by:xiaofengsheng at 2009-04-24 18:30:55
> 2
> 
> 3 8 7 2
> 6 14 6
> 4 10 4
> 5 14 2
> 
> 1 6 10 20
> 2 3 5
> 
> answer:
> 17 10

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

struct Board
{
	int left;
	int right;
	int height;
	int left_next_index;
	int right_next_index;
};

bool sort_by_height_descending(Board b1, Board b2)
{
	return b1.height > b2.height;
}

const int N = 1024;
Board a[N];
int dp_left[N];
int dp_right[N];

int search(int i, int x, int y, int n, int m)
{
	if (i <= n)
	{
		if (x >= a[i].left && x <= a[i].right && y - a[i].height <= m)
		{
			if (dp_left[i] == -1)
			{
				dp_left[i] = search(a[i].left_next_index, a[i].left, a[i].height, n, m);
			}
			int left = dp_left[i] + x - a[i].left;
			if (dp_right[i] == -1)
			{
				dp_right[i] = search(a[i].right_next_index, a[i].right, a[i].height, n, m);
			}
			int right = dp_right[i] + a[i].right - x;
			return min(left, right) + y - a[i].height;
		} 
		else
		{
			return search(i + 1, x, y, n, m);
		}
	} 
	else
	{
		if (y > m)
		{
			return 0x7f7f7f7f;
		} 
		else
		{
			return y;
		}
	}
}

int main()
{
	int t;
	cin>>t;
	while (t--)
	{
		int n, x, y, m;
		cin>>n>>x>>y>>m;
		for (int i=1; i<=n; i++)
		{
			cin>>a[i].left>>a[i].right>>a[i].height;
		}
		sort(a + 1, a + n + 1, sort_by_height_descending);

		for (int i=1; i<=n; i++)
		{
			a[i].left_next_index = n + 1;
			for (int j=i+1; j<=n; j++)
			{
				if (a[j].left <= a[i].left)
				{
					a[i].left_next_index = j;
					break;
				}
			}
			a[i].right_next_index = n + 1;
			for (int j=i+1; j<=n; j++)
			{
				if (a[j].right >= a[i].right)
				{
					a[i].right_next_index = j;
					break;
				}
			}
		}

		memset(dp_left, -1, sizeof(int) * N);
		memset(dp_right, -1, sizeof(int) * N);
		cout<<search(1, x, y, n, m)<<endl;
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator