Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 谢谢，用这数据找到了程序问题，一次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
>
> 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:

User ID:
Title:

Content: