XMOJ3065 旅游线路

10分钟没啥思路就去看题解了，结果发现很蠢。

题目大意

有一条河，河的东侧和西侧分别有 $n,m$ 个景点，每个景点有个权值。有 $k$ 条船，每条船连接东侧和西侧的一个景点。定义一个旅游线路是通过船连接起来的景点序列。一个旅游线路合法当且仅当线路中任意两条船不相交，即不存在两条船 $(x_1,y_1)$， $(x_2,y_2)$使得 $x_1＞x_2$ 并且 $y_1＜y_2$ ，或者 $x_1=x_2,y_1=y_2$。一个旅游线路的权值定义为线路中所有景点权值之和，求美丽值最大的合法旅游线路。

$n,m\le 40000$，$k\le 10^5$。

题解

发现一条合法线路当且仅当下一个东侧点大于上一个东侧点，下一个西侧点大于上一个西侧点，也就是“z”形走位。

于是将每条边排序，东侧点为第一关键字，西侧点为第二关键字，这样可以保证每次选的边都和前面不相交。因为对于走到某个东侧点时，西侧点比他小的总是先被选完，而对于一个西侧点也同理。

然后就可以直接dp了。

感觉这个排序很神奇，明明思路很直接但就是一下子没想到。太聪明了。

Code

#include<bits/stdc++.h>
using namespace std;const int N=40000+5,M=1e5+5,INF=1e9;int n,m,k,ans,a[N],b[N],f[N][2];struct giao{int a,b;
}c[M];bool cmp(giao x,giao y){return x.a!=y.a?x.a<y.a:x.b<y.b; 
}int main(){freopen("route.in","r",stdin);freopen("route.out","w",stdout);scanf("%d%d%d",&n,&m,&k);for(int i=1;i<=n;i++){scanf("%d",&a[i]);f[i][0]=a[i];ans=max(ans,a[i]);}for(int i=1;i<=m;i++){scanf("%d",&b[i]);f[i][1]=b[i];ans=max(ans,b[i]);}for(int i=1;i<=k;i++)scanf("%d%d",&c[i].a,&c[i].b);sort(c+1,c+1+k,cmp);for(int i=1;i<=k;i++){int sa=f[c[i].b][1]+a[c[i].a],sb=f[c[i].a][0]+b[c[i].b];f[c[i].a][0]=max(f[c[i].a][0],sa);f[c[i].b][1]=max(f[c[i].b][1],sb);ans=max(ans,max(f[c[i].a][0],f[c[i].b][1]));}printf("%d",ans);return 0;
}