题解
:
一开始想到了最长递增序列
,但这样写需要用n
-max.dp
[],会出现
一些其他的情况考虑，怪我比较嫌麻烦，然后就想到了求最长递减
序列
然后交了一发TLE
TLE代码
:
using namespace std
;
struct node
{
int lon
;//长度
int m_g
;//质量
} temp
[maxn
];
bool cmp(node x
,node y
)
{
if(x
.lon
==y
.lon
)
{
return x
.m_g
<y
.m_g
;
}
return x
.lon
<y
.lon
;
}
int n
;
int dp
[maxn
];
void s_dp
()
{
for(int i
=1; i
<=n
; i
++)
{
dp
[i
]=1;
for(int j
=1; j
<i
; j
++)
{
if(temp
[j
].m_g
>temp
[i
].m_g
)
{
dp
[i
]=max(dp
[i
],dp
[j
]+1);
}
}
}
int maxx
=-1;
for(int i
=1;i
<=n
;i
++)
{
if(dp
[i
]>maxx
)
{
maxx
=dp
[i
];
}
}
printf
("%d\n",maxx
);
}
int main
()
{
int t
;
scanf
("%d",&t
);
while(t
--)
{
memset
(dp
,0,sizeof
(dp
));
scanf
("%d",&n
);
for(int i
=1;i
<=n
;i
++)
{
scanf
("%d %d",&temp
[i
].lon
,&temp
[i
].m_g
);
}
sort
(temp
+1,temp
+n
+1,cmp);//排序
s_dp
();
}
}
虽然当时想着会T但是还是想试一发，然后就优化呗，二分求解最长
递减序列
AC代码
:
using namespace std
;
struct node
{
int lon
;//长度
int m_g
;//质量
} temp
[maxn
];
int Stack
[maxn
];
bool cmp(node x
,node y
)
{
if(x
.lon
==y
.lon
)
{
return x
.m_g
<y
.m_g
;
}
return x
.lon
<y
.lon
;
}
int lower_s
(int l
,int r
,int i
)
{
while(l
<=r
)
{
int mid
=(l
+r
)/2;
if(Stack
[mid
]<=temp
[i
].m_g
)
{
r
=mid
-1;
}
else
{
l
=mid
+1;
}
}
return l
;
}
int n
;
int dp
[maxn
];
void s_dp
()
{
int top
=1;
Stack
[top
]=temp
[1].m_g
;
for(int i
=2; i
<=n
; i
++)
{
if(Stack
[top
]>temp
[i
].m_g
)
{
Stack
[++top
]=temp
[i
].m_g
;
}
else
{
Stack
[lower_s
(1,top
,i
)]=temp
[i
].m_g
;
}
}
printf
("%d\n",top
);
}
int main
()
{
int t
;
scanf
("%d",&t
);
while(t
--)
{
memset
(Stack
,0,sizeof
(Stack
));
scanf
("%d",&n
);
for(int i
=1;i
<=n
;i
++)
{
scanf
("%d %d",&temp
[i
].lon
,&temp
[i
].m_g
);
}
sort
(temp
+1,temp
+n
+1,cmp);//排序
s_dp
();
}
}
