最近水两道acm的题,发现好久不写题,的确不行了,都忘光了。
就是水题也得卡个半死。

祝西电同学们今天网赛发挥出色!

//每个平台看做两个点,左端和右端。
//dp[i][0],dp[i][1]分别表示从上往下,到第i个平台的左右端点的最短时间。
#include
<iostream>
#include
<cstdio>
#include
<algorithm>
using namespace std;
struct node
{
    
int l,r,h;
}t[
1010];
int cas,n,X,Y,MAX;
int dp[1010][2];
bool cmp( node a,node b)
{
    
return a.h>b.h;
}
int main()
{
    scanf(
"%d",&cas);
    
while(cas--)
    {
        scanf(
"%d%d%d%d",&n,&X,&Y,&MAX);
        
for(int i=1;i<=n;i++)
                scanf(
"%d%d%d",&t[i].l,&t[i].r,&t[i].h);
        sort(t
+1,t+1+n,cmp);
        memset(dp,
0x3f,sizeof(dp));
        
int start=0;
        t[
0].l=t[0].r=X;
        t[
0].h=Y;
        dp[
0][0]=dp[0][1]=0;
        
for(int i=0;i<=n;i++)
        {
            
for(int j=i+1;j<=n;j++)
            {
                
if(t[i].h-t[j].h<=MAX)
                {
                    
if(t[i].l>=t[j].l&&t[i].l<=t[j].r)
                    {
                        dp[j][
0]=min(dp[j][0],dp[i][0]+t[i].l-t[j].l+t[i].h-t[j].h);
                        dp[j][
1]=min(dp[j][1],dp[i][0]+t[j].r-t[i].l+t[i].h-t[j].h);
                        
break;
                    }
                }
            }
            
for(int j=i+1;j<=n;j++)
            {
                
if(t[i].h-t[j].h<=MAX)
                {
                    
if(t[i].r>=t[j].l&&t[i].r<=t[j].r)
                    {
                        dp[j][
0]=min(dp[j][0],dp[i][1]+t[i].r-t[j].l+t[i].h-t[j].h);
                        dp[j][
1]=min(dp[j][1],dp[i][1]+t[j].r-t[i].r+t[i].h-t[j].h);
                        
break;
                    }
                }
            }
        }
        
int mi=100000000;
        
for(int i=n;i>=0;i--)
        {
            
if(t[i].h>MAX)
                
break;
            
bool flag=0;
            
for(int j=i+1;j<=n;j++)
            
if(t[j].l<=t[i].l&&t[j].r>=t[i].l)
            {
                flag
=1;
                
break;
            }
            
if(!flag)
                mi
=min(mi,dp[i][0]+t[i].h);
            flag
=0;                
            
for(int j=i+1;j<=n;j++)
                
if(t[j].l<=t[i].r&&t[j].r>=t[i].r)
                {
                    flag
=1;
                    
break;
                }
            
if(!flag)
                mi
=min(mi,dp[i][1]+t[i].h);
        }
        printf(
"%d\n",mi);
    }
}