3234196_ac_0ms_292k.cc

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <algorithm>
#define min(a,b) a < b ? a : b
using namespace std;

struct node
{
	int l, r, h;
	bool operator < (const node &x) const
	{
		return h > x.h;
	}
};

node flat[1010];
int dp[1010][2];
int n;

int main()
{
	int i, j, t0, t1;
	int cas, max;

	scanf("%d",&cas);
	while(cas-- > 0)
	{
		scanf("%d%d%d%d",&n,&flat[0].l,&flat[0].h,&max);
		flat[0].r = flat[0].l;
		for(i = 1; i <= n; i++)
		{
			scanf("%d%d%d",&flat[i].l,&flat[i].r,&flat[i].h);
		}
		++n;
		flat[n].l = -100000;flat[n].r = 100000;
		flat[n].h = 0;
		sort(flat,flat+n+1);
		memset(dp,-1,sizeof(dp));
		dp[0][0] = dp[0][1] = 0;
		for(i = 0; i < n; i++)
		{
			for(j = i+1; j <= n; j++)
			{
				if(dp[i][0]==-1||flat[j].h < flat[i].h - max)
					break;
				if(flat[i].h==flat[j].h)
					continue;
				if(flat[j].l<=flat[i].l&&flat[i].l<=flat[j].r)
				{
					t0 = t1 = dp[i][0]+flat[i].h-flat[j].h;
					if(j!=n)
					{
						t0 += flat[i].l-flat[j].l;
						t1 += flat[j].r-flat[i].l;
					}
					if(dp[j][0]==-1||t0<dp[j][0])
					{
						dp[j][0] = t0;
					}
					if(dp[j][1]==-1||t1<dp[j][1])
					{
						dp[j][1] = t1;
					}
					break;
				}
			}
			for(j = i+1; j <= n; j++)
			{
				if(dp[i][1]==-1||flat[j].h < flat[i].h - max)
					break;
				if(flat[i].h==flat[j].h)
					continue;
				if(flat[j].l<=flat[i].r&&flat[i].r<=flat[j].r)
				{
					t0 = t1 = dp[i][1]+flat[i].h-flat[j].h;
					if(j!=n)
					{
						t0 += flat[i].r-flat[j].l;
						t1 += flat[j].r-flat[i].r;
					}
					if(dp[j][0]==-1||t0<dp[j][0])
					{
						dp[j][0] = t0;
					}
					if(dp[j][1]==-1||t1<dp[j][1])
					{
						dp[j][1] = t1;
					}
					break;
				}
			}
		}
		int ans;
		if(dp[n][0]==-1)
			ans = dp[n][1];
		else
		{
			if(dp[n][1]==-1)
				ans = dp[n][0];
			else
				ans = min(dp[n][0],dp[n][1]);
		}
		printf("%d\n",ans);
	}
	return 0;
}