重庆做营销网站太原网站建设方案咨询
10分钟没啥思路就去看题解了，结果发现很蠢。
题目大意
有一条河，河的东侧和西侧分别有 n , m n,m n,m 个景点，每个景点有个权值。有 k k k 条船，每条船连接东侧和西侧的一个景点。定义一个旅游线路是通过船连接起来的景点序列。一个旅游线路合法当且仅当线路中任意两条船不相交，即不存在两条船 ( x 1 , y 1 ) (x_1,y_1) (x1,y1)， ( x 2 , y 2 ) (x_2,y_2) (x2,y2)使得 x 1 ＞ x 2 x_1＞x_2 x1＞x2 并且 y 1 ＜ y 2 y_1＜y_2 y1＜y2 ，或者 x 1 = x 2 , y 1 = y 2 x_1=x_2,y_1=y_2 x1=x2,y1=y2。一个旅游线路的权值定义为线路中所有景点权值之和，求美丽值最大的合法旅游线路。
n , m ≤ 40000 n,m≤40000 n,m≤40000， k ≤ 1 0 5 k≤10^5 k≤105。
题解
发现一条合法线路当且仅当下一个东侧点大于上一个东侧点，下一个西侧点大于上一个西侧点，也就是“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;
}